程序设计基础

11.1 单词索引

例11-1. 单词索引

一个单词表存放了5个表示颜色的英文单词，输入一个字母，在单词表中查找并输出所有以此字母开头的单词，若没有找到，输出Not Found

11.1.1 程序解析

                        
#include<stdio.h>
int main()
{
    int i, flag=0;
    char ch;
    const char* color[5]={"red", "blue", "yellow", "green", "black"};  /* 指针数组 */

    printf("INput a letter: ");
    ch=getchar();
    for(i=0; i<5; i++)
    {
            if(*color[i]==ch){  /* 获得当前的字符 */
                flag=1;
                puts(color[i]);  /* 输出数组的第i项，即单词 */
            }
    }
    if(flag==0)
        printf("Not Found\n");
    return 0;
}
                        
                    

11.1.2 指针数组的概念

C语言中的数组可以是任何类型，如果数组的各个元素都是指针类型，用于存放内存地址，这个数组就是指针数组
一维指针数组的定义一般为
类型名 *数组名[数组长度]
int a[10]; /* a是一个数组，有10个元素，每个元素的类型都是整型 */
char* color[5]; /* color是一个数组，有5个元素，为每个元素的类型都是字符指针 */

指针数组解析

const char* color[5]={"red", "blue", "yellow", "green", "black"};
color是一个数组，有5个元素
每个元素的类型都是指针
数组元素可以处理字符串(字符串vs字符指针)
const的作用是限定变量的值不能改变，即常量

指针数组操作

对指针数组元素的操作和对同类型指针变量的操作完全相同
    printf("%s %x\n", color[i], color[i]);
继续执行以下语句，功能是什么?
    char *tmp;
    tmp=color[0];
    color[0]=color[4];
    color[4]=tmp;

• 指针数组可以直接对数组元素进行引用操作，
  tmp=color[0];
• 也可以间接访问操作数组元素所指向的单元内容:
  printf("%c", *(color[i]+1));

指向指针的指针(二级指针)

指向指针的指针(二级指针)的一般定义为:
类型名 **变量名;

二级指针操作示例

例11-2. 二级指针操作

对下列变量定义和初始化后，依次执行操作①-③后，各变量的值分别为什么?

二级指针操作解析

二维数组的指针形式

int a[3][4];
可以看成是由a[0],a[1],a[2]组成的一维数组
a[0],a[1],a[2]各自又是一个一维数组
二维数组是数组元素为一维数组的一维数组

a: 第0行地址(行地址)
a+i: 第i行的地址
*(a+i)/a[i]: 第i行首元素的地址
*(a+i)+j/a[i]+j: 第i行第j个元素的地址
**(a+i)/a[i][0]: 第i行首元素的值
*(*(a+i)+j)/a[i][j]: 第i行第j个元素的值

单词索引二级指针实现

例11-3. 使用二维指针改写例11-1.

                        
#include<stdio.h>
int main()
{
    int i, flag=0;
    char ch;
    const char* color[5]={"red", "blue", "yellow", "green", "black"};

    const char** pc;  /* 定义二级指针 */
    pc=color;  /* 二级指针赋值 */
    printf("Input a letter: ");
    ch=getchar();
    for(i=0; i<5; i++){
        if(**(pc+i)==ch){  /* 使用二级指针操作数组 */
            flag=1;
            puts(*(pc+i));  /* 输出字符串 */
        }
    }
    if(flag==0)
        printf("Not Found\n");
    return 0;
}
                        
                    

单词索引二级指针解析

11.1.4 用指针数组处理多个字符串

指针数组与二维数组 --> 使用指针数组更节省空间

char ccolor[][7]={"red", "blue", "yellow", "green", "black"};

char *pcolor[]={"red", "blue", "yellow", "green", "black"};

用指针数组操作多个字符串

例11-4. 将5个字符串从小到大排序后输出

                        
#include<stdio.h>
#include<string.h>
void fsort(const char* color[], int n)
{
    int k, j;
    const char *temp;
    for(k=1; k<=n; k++){
        for(j=0; j<=n-k; j++){
            if(strcmp(color[j], color[j+1])<0){
                temp=color[j];
                color[j]=color[j+1];
                color[j+1]=temp;
            }
        }
    }
}

int main()
{
    int i;
    const char* pcolor[5]={"red", "blue", "yellow", "green", "black"};
    fsort(pcolor, 5);
    for(i=0; i<5; i++)
        printf("%s ", pcolor[i]);
    return 0;
}
                        
                    

排序函数对比

                            
void fsort(const char* color[], int n)
{
    int k, j;
    const char *temp;
    for(k=1; k<=n; k++){
        for(j=0; j<n-k; j++){
            if(strcmp(color[j], color[j+1])<0){
                temp=color[j];
                color[j]=color[j+1];
                color[j+1]=temp;
            }
        }
    }
}
                            
                        

                            
void fsort(int a[], int n)
{
    int k, j;
    int temp;
    for(k=1; k<=n; k++){
        for(j=0; j<n-k; j++){
            if(a[j]>a[j+1]){
                temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}
                            
                        

指针数组排序后结果对比

排序前

排序后

动态输入多个字符串

例11-5. 解密英文藏头诗

将一首诗的每一句的第一个字连起来，所组成的内容就是该诗的真正含义
输入的藏头读小于20行，每行不超过80个字符，以#作为输入的结束标志，使用动态内存分配方式处理字符串的输入

藏头诗源程序

                        
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int main()
{
    int i, n=0;
    char *poem[20], str[80], mean[20];  /* poem用于存放每一行，str用于存放一行输入内容，mean用于存放每一行的第一个字 */

    gets(str);
    wihle(str[0]!='#'){  /* 一行不以'#'结束，为有效输入 */
        poem[n]=(char*)malloc(sizeof(char)*(strlen(str)+1));  /* 动态分配一行字符串大小的空间 */
        strcpy(poem[n], str);  /* 将输入的字符串赋值给动态内存单元 */
        n++;
        gets(str);
    }
    for(i=0; i<n; i++){
        mean[i]=*poem[i];  /* 每行取第一个字符 */
        free(poem[i]);  /* 释放动态分配的内存单元 */
    }
    mean[i]='\0';
    puts(mean);
    return 0;
}
                        
                    

指针综合应用

例11-6. 随机发牌

一副纸牌有52张，4种花色，每种花色13张。用程序模拟随机发牌过程，将52张牌按轮转的方式发放给4人，并输出发牌结果

随机发牌源程序(1)

                        
#include<stdio.h>
#include<stdlib.h>
#include<time.h>

struct card{
    int suit;  /* 花色 */
    int face;  /* 牌点 */
};
void deal(struct card *wdeck)
{
    int i, m, t;
    static int temp[52]={0};  /* 发牌标记，0表示未发，1表示已发 */
    srand(time(NULL));  /* 设置随机数的产生与系统时钟关联 */
    for(i=0; i<52; i++){
        while(1)
        {
            m=rand()%52;  /* 生成一个随机数，介于0~51之间 */
            if(temp[m]==0)
                break;
        }
        temp[m]=1;
        /* 4人轮转发牌 */
        t=(i%4)*13+(i/4);
        wdeck[t].suit=m/13;
        wdeck[t].face=m%13;
        }
    }
}
                        
                    

随机发牌源程序(2)

                        
int main()
{
    int i;
    struct card deck[52];
    const char* suit[]={"Heart", "Diamond", "Club", "Spade"};
    const char* face[]={"A","K","Q","J","10","9","8","7","6","5","4","3","2"};

    deal(deck);
    for(i=0; i<52; i++){
        if(i%13==0)
            printf("Player %d:\n", i/13+1);
        printf("%s of %s\n", face[deck[i].face], suit[deck[i].suit]);
    }
    return 0;
}
                        
                    

11.1.5 命令行参数

• C语言源程序经过编译和连接处理，生成可执行程序如text.exe后，才能运行
• 在DOS环境的命令窗口中，输入可执行文件名，就可以以命令方式运行该程序
• 输入这些命令时，在可执行文件(命令)名后可以跟一些参数，这些参数被称为命令行参数
  如:
  ping www.baidu.com
  ping -t www.baidu.com
  ping -n 6 www.baidu.com
  ping -h

命令行参数的形式

命令行参数的一般形式为
命令名 参数1 参数2 ... 参数n
命令名和各参数之间用空格分隔，也可以没有参数
用命令行的程序不能在编译器中执行，需要将源程序经编译、链接成相应的命令文件，回到命令行状态，再在该状态下直接输入命令文件名

带参数的main()函数格式

int main(int argc, char* argv[])
第1个参数argc接收命令行参数的个数(包含命令名)
第2个参数argv接收以字符串常量形式存储的命令行参数(包括命令名本身)
如
ping www.baidu.com argc的值为2，argv为"ping", "www.baidu.com"
ping -t www.baidu.com argc的值为3，argv为"ping", "-t", "www.baidu.com"
ping -n 6 www.baidu.com argc的值为4，argv为"ping", "-n", "6", "www.baidu.com"

命令行参数示例

例11-7. echo

将所有命令行参数在同一行输出

                        
#include<stdio.h>
int main(int argc, char *argv[])
{
    int k;
    for(k=1; k<argc; k++)
        printf("%s ", argv[k]);
    printf("\n");
    return 0;
}
                        
                    

11.2 字符定位

例11-8. 字符定位

输入一个字符串和一个字符，如果该字符在字符串中，就从该字符首次出现的位置开始输出字符串中的字符。要求定义函数match(char* s, char chp)，在字符串s中查找字符ch，如果找到则返回第一次找到的该字符在字符串中的位置(地址)，否则，返回空指针NULL。如输入字符串program和字符r，输出rogram

11.2.1 程序解析

                        
#include<stdio.h>
char* match(char* s, char ch)  /* match返回值为一个指针 */
{
    while(*s!='\0'){
        if(*s==ch)
            return s;
        s++;
    }
    return NULL;
}
int main()
{
    char ch, str[80], *p=NULL;
    printf("Input the string:");
    scanf("%s", str);
    getchar();
    printf("Input a character:");
    ch=getchar();
    if((p=match(str, ch))!=NULL)  /* 指针p接收match的返回值 */
        printf("%s\n", p);  /* 输出指针所指处的内容，直到'\0' */
    else
        printf("Not Found\n");
    return 0;
}
                        
                    

11.2.2 指针作为函数的返回值

函数返回值的类型可以有：
整型, 浮点型，字符型, 结构类型型，指针类型
在C语言中，函数返回值也可以是指针，定义和调用这类函数的方法与其他函数是一样的

指针作为函数返回值解析

思考，在例11-8中，如果把str的定义和相应的数据输入都放在函数match()中，结果会如何?

                        
char* match()
{
    char ch, str[80], *s=str;
    scanf("%s", str);
    getchar();
    ch=getchar();
    while(*s!='\0'){
        if(*s==ch)
            return s;
        s++;
    }
    return NULL;
}
                        
                    

不能返回在函数内部定义的局部数据对象的地址，所有的局部数据对象在函数返回时都会消亡，其值不再有效
返回指针的函数一般都返回全局数据对象或主调函数中数据对象的地址

11.2.3 指向函数的指针

函数指针的定义

类型名 (*变量名)(参数类型表)
类型名指定函数返回值的类型，变量名指向函数的指针变量的名称，参数类型表指的函数的参数类型列表，例如
int (*funptr)(int, int)
定义的是一个函数指针funptr，它可以指向有两个整数类型参数，并且返回类型为int的函数

通过函数指针调用函数

通过函数指针调用函数的一般格式为
(*函数指针名)(参数表)
例如
int fun(int x, int y);
int (*funptr)(int, int);
funptr=fun;
int num=(*funptr)(3,5);

函数指针作为函数的参数

C语言的函数调用中，函数名或已赋值的函数指针也能作为实参，此时，形参就是函数指针，它指向实参所代表函数的入口地址，例如
int fun(int x, int y)
{...}
f(int (*funptr)(int,int))
{...}
void main()
{...
    int (*funptr)(int, int);
    funptr=fun;
    f(funptr);
    ......
}

指向函数的指针示例

例11-9. 函数指针示例

编写一个函数calc(f, a, b)，用梯形公式求函数$f(x)$在[a,b]上的数值积分 $$ \int_{b}^{a}f(x)dx=(b-a)/2\times(f(a)+f(b)) $$ 然后调用该函数计算下列数值积分(用函数指针作为函数参数示例)
① $\int_{0}^{1}x^2dx$    ②$\int_{1}^{2}\sin{x}/xdx$

函数指针示例源代码

                        
#include<stdio.h>
#include<math.h>
double calc(double (*funp)(double), double a, double b)
{
    double z;
    z=(b-a)/(2*((*funp)(a)+(*funp)(b)));  /* 调用funp指向的函数 */
    return z;
}
double f1(double x)
{
    return x*x;
}
double f2(double x)
{
    return sin(x)/x;
}
int main()
{
    double result;
    double (*funp)(double);
    result=calc(f1, 0.0, 1.0);  /* 把函数名f1作为函数calc的实参 */
    printf("1: result=%.4f\n", result);
    funp=f2;  /* 对函数指针funp赋值 */
    result=calc(funp, 1.0, 2.0);  /* 函数指针funp作为函数calc的实参 */
    printf("2: result=%.4f\n", result);
    return 0;
}
                        
                    

用链表构建学生信息库

例11-10. 学生成绩信息库

建立一个学生成绩信息的单向链表，包括学号、姓名、成绩等，学生记录按学号由小到大顺序排列，要求实现对成绩信息的插入、修改、删除和遍历操作

11.3.1 程序解析(1)

                        
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct stud_node{
    int num;
    char name[20];
    int score;
    struct stud_node *next;
};

/* 新建链表 */
struct stud_node* create_stu_Doc()
{
    struct stud_node *head, *p;
    int num, score;
    char name[20];
    int size=sizeof(struct stud_node);

    head=NULL;
    printf("Input num, name and score:");
    scanf("%d%s%d", &num, name, &score);
    while(num!=0){
        p=(struct stud_node*)malloc(size);  /* 动态分配内存 */
        p->num=num;
        strcpy(p->name, name);
        p->score=score;
        head=insertDoc(head, p);  /* 调用插入函数 */
        printf("Input num, name and score:");
        scanf("%d%s%d", &num, name, &score);
    }
    return 0;
}
                        
                    

程序解析(2)

                        
struct stud_node* insertDoc(struct stud_node *head, struct stud_node *stud)
{
    struct stud_node *ptr, *ptr1, *ptr2;  /* 插入链表，需要三个指针，分别指向当前，前一个以及后一个 */
    ptr2=head;
    ptr=stud;

    /* 原链表为空时插入 */
    if(head==NULL){
        head=ptr;
        head->next=NULL;
    }else{
        while((ptr->num>ptr2->num) && (ptr2->next!=NULL)){
            ptr1=ptr2;  /* ptr1, ptr2分别往后移一个结点 */
            ptr2=ptr2->next;
        }
        if(ptr->num<=ptr2->num){  /* 在ptr1和ptr2之间插入新结点 */
            if(head==ptr2)
                head=ptr;
            else
                ptr1->next=ptr;
            ptr->next=ptr2;
        }
        else{
            ptr2->next=ptr;
            ptr->next=NULL;
        }
    }
    return head;
}
                        
                    

程序解析(3)

                        
struct stud_node* deleteDoc(struct stud_node* head, int num)
{
    struct stud_node *ptr1, *ptr2;
    /* 要被删除的结点为表头结点 */
    while(head!=NULL && head->num==num){
        ptr2=head;
        head=head->next;
        free(ptr2);
    }
    if(head==NULL)  /* 链表空 */
        return NULL;
    /* 要被删除的结点为非表头结点 */
    ptr1=head;
    ptr2=head->next;  /* 从表头的下一个结点搜索所有符合条件的结点 */
    while(ptr2!=NULL){
        if(ptr2->num==num){  /* ptr2指向要删除的结点 */
            ptr1->next=ptr2->next;
            free(ptr2);
        }
        else{
            ptr1=ptr2;
            ptr2=ptr2->next;
        }
    }
    return head;
}
                        
                    

程序解析(4)

                        
void print_stu_doc(struct stud_node *head)
{
    struct stud_node *ptr;
    if(head==NULL){
        printf("\nNo Records \n");
        return;
    }
    printf("\nThe students' Records are:\n");
    printf("Num\t Name\t Score \n");
    for(ptr=head; ptr!=NULL; ptr=ptr->next)
        printf("%d\t %s\t %d\n", ptr->num, ptr->name, ptr->score);
}
                        
                    

程序解析(5)

                        
int main()
{
    struct stud_node *head, *p;
    int choice, name, score;
    char name[20];
    int size=sizeof(struct stud_node);

    do{
        printf("1. Create\n2. Insert\n3. Delete\n4. Print\n0. Exit\n");
        scanf("%d", &choice);
        switch(choice){
            case 1:
                head=create_stu_Doc();
                break;
            case 2:
                printf("Input num, name and score:\n");
                scanf("%d%s%d", &num, name, &score);
                p=(struct stud_node*)malloc(size);
                p->num=num;
                strcpy(p->name, name);
                p->score=score;
                head=insertDoc(head, p);
                break;
            case 3:
                printf("Input num:\n");
                scanf("%d", &num);
                head=deleteDoc(head, num);
                break;
            case 4:
                print_stu_doc(head);
                break;
            default:
                break;
        }
    }while(choice!=0);
    return 0;
}
                        
                    

链表的概念

链表定义

一般使用结构定义单向链表结点的数据类型，采用结构的递归定义
struct stud_node{
    int num;
    char name[20];
    int score;
    struct stud_node* next;
}

单向链表VS数组

• 在用数组存放数据时，一般需要事先定义固定长度的数组，在数组元素个数不确定时，可能会浪费内存空间
• 链表为动态存储分布的数据结构，可根据需要动态开辟内存空间，可以比较自由方便地插入新元素(结点)，故使用链表可以节省内存，操作效率高

动态分配相关函数

• void* malloc(unsigned size)
  功能：在内存的动态存储区中分配一块长度为size的连续空间
  返回值：指针，存放被分配内存的起始地址，若未申请到空间，则返回NULL(0)
  例如:
  (int*) malloc(sizeof(int));
  (struct student*)malloc(sizeof(struct student))
• void free(void* ptr)
  功能：释放由malloc申请的动态内存空间，ptr存放该空间的首地址
  返回值：无
  例如：free(p);

11.3.3 单向链表的常用操作

建立链表

链表的建立

                        
head=tail=NULL;
scanf("%d%s%d", &num, name, &score);
while(num!=NULL){
    p=(struct stud_node*)malloc(size);
    p->num=num;
    strcpy(p->name, name);
    p->score=score;
    scanf("%d%s%d", &num, name, &score);
}
                        
                    

                            
p->next=NULL;
if(head==NULL)
    head=p;
else
    tail->next=p;
tail=p;
                            
                        

                            
p->next=head;
head=p;
                            
                        

链表的遍历

                        
for(ptr=head; ptr!=NULL; ptr=ptr->next)
    printf("%d\t%s\t%d\n", ptr->num, ptr->name, ptr->score);
                        
                    

插入结点

先连: s->next=ptr->next
后断: ptr->next=s;

删除结点

ptr2=ptr1->next;
先接: : ptr1->next=ptr2->next;
后删: : free(ptr2);