指針與鏈表的理解

 一、指針的概括

1.指針的類型

      基本數據類型比如 int、char ，還有 一些復雜的比如 int （*p）[], 指向數組的指針，像這種的判斷就是指針名字去掉 ， 指針的類型類型就是 int（*）[]，其實就是指向數組的指針

 2.指針所指向的類型

      當你通過指針來訪問指針所指向的內存區時，指針所指向的類型決定了編譯器將把那片內存區里的內容當做什么來看待。  你只須把指針聲明語句中的指針名字和名字左邊的指針聲明符*去掉，剩下的就是指針所指向的類型。

     例如：int*ptr：指針所指向的類型是int   int(*ptr)[3]：指針所指向的的類型是int()[3] 

   3.指針的值

     我們說一個指針的值是XX，就相當于說該指針指向了以XX為首地址的一片內存區域；我們說一個指針指向了某塊內存區域，就相當于說該指針的值是這塊內存區域的首地址。 

例如：一個簡單的指針：

#include<stdio.h>

int main()

{

   int *ptr;   // 聲明一個int指針

   int val = 1;  // 聲明一個int值

   ptr = &val;  // 為指針分配一個int值的引用

   int deref = *ptr;  // 對指針進行取值，打印存儲在指針地址中的內容

   printf("deref地址=%ld,值=%d\n",ptr, deref);

}

就像數組一樣，指向結構體的指針存儲了結構體第一個元素的內存地址。與數組指針一樣，結構體的指針必須聲明和結構體類型保持一致，或者聲明為void類型。

例如：

#include<stdio.h>

struct person {

  int age;

  char *name;

};

int main()

{

  struct person first;

  struct person *ptr;

  first.age = 21;

  char *fullname = "full name";

  first.name = fullname;

  ptr = &first;

  printf("age=%d, name=%s\n", first.age, ptr->name);

二、鏈表概述 　　

   1. 鏈表是一種常見的重要的數據結構。

         它是動態地進行存儲分配的一種結構。它可以根據需要開辟內存單元。鏈表有一個“頭指針”變量，以head表示，它存放一個地址。該地址指向一個元素。鏈表中每一個元素稱為“結點”，每個結點都應包括兩個部分：一為用戶需要用的實際數據，二為下一個結點的地址。因此，head指向第一個元素：第一個元素又指向第二個元素；……，直到最后一個元素，該元素不再指向其它元素，它稱為“表尾”，它的地址部分放一個“NULL”（表示“空地址”），鏈表到此結束。       

2.  鏈表的各類操作包括：

      學習單向鏈表的創建、刪除、  插入（無序、有序）、輸出、  排序（選擇、插入、冒泡）、反序等等。

例如：

#include <stdio.h>  

#include <conio.h>  

#include <string.h>  

#include <stdlib.h>

#define N 3 /*N為人數*/

typedef struct node

{

   char name[20];

   struct node *link;

}stud;

stud * creat(int n) /*建立單鏈表的函數，形參n為人數*/

{

   stud *p,*h,*s; /* *h保存表頭結點的指針，*p指向當前結點的前一個結點，*s指向當前結點*/

   int i; /*計數器*/

   if((h=(stud *)malloc(sizeof(stud)))==NULL) /*分配空間并檢測*/

   {

     printf("不能分配內存空間!");

     exit(0);

   }

   h->name[0]='\0'; /*把表頭結點的數據域置空*/

   h->link=NULL; /*把表頭結點的鏈域置空*/

   p=h; /*p指向表頭結點*/

   for(i=0;i<N;i++)

   {

     if((s= (stud *) malloc(sizeof(stud)))==NULL) /*分配新存儲空間并檢測*/

     {

        printf("不能分配內存空間!");

        exit(0);

     }

     p->link=s; /*把s的地址賦給p所指向的結點的鏈域，這樣就把p和s所指向的結點連接起來了*/

     printf("請輸入第%d個人的姓名",i+1);

     scanf("%s",s->name); /*在當前結點s的數據域中存儲姓名*/

     s->link=NULL;

     p=s;  //要把s的數據保存到p中，要不下次循環s就又指向一個空的新地址了。

   }

   return(h);

}

int main()

{

   int number; /*保存人數的變量*/

   stud *head; /*head是保存單鏈表的表頭結點地址的指針*/

   number=N;

   head=creat(number); /*把所新建的單鏈表表頭地址賦給head*/

}

三、高中學生成績信息統計系統（例子）

#include <stdio.h>  

#include <conio.h>  

#include <string.h>  

#include <stdlib.h>  

typedef struct Node Node;  

//定義成績信息節點

//分別為語文、數學、英語、物理、化學和總成績；

struct Score  

{  

    int chinese,math,english,physics,chemistry,sum;  

};  

//定義學生信息節點

//分別為姓名、班級、學號、成績和指向下一個節點的指針

//定義了4個全局變量，頭節點，和臨時節點變量；

struct Node  

{  

    char name[20],classs[20],number[20];  

    struct Score score;  

    struct Node* next;  

}*head,*u,*p,*q;  

  //定義多個學生的學生個數及各科平均成績優秀率及格率；

int n,C,M,E,D,F,Cj,Cy,Mj,My,Ej,Ey,Dj,Dy,Fj,Fy;  

char num[20];  

//進入菜單函數

void Welcome()  

{  

    printf("\t\t      # # # # # # # # # # # # # # # # #\n");  

    printf("\t\t      #   歡迎您使用學生成績管理系統 #\n");  

    printf("\t\t      #                              #\n");  

    printf("\t\t      #         1.讀取文件           #\n");  

    printf("\t\t      #                              #\n");  

    printf("\t\t      #         2.保存文件           #\n");  

    printf("\t\t      #                              #\n");  

    printf("\t\t      #         3.添加學生成績       #\n");  

    printf("\t\t      #                              #\n");  

    printf("\t\t      #         4.修改學生成績       #\n");  

    printf("\t\t      #                              #\n");  

    printf("\t\t      #         5.刪除學生成績       #\n");  

    printf("\t\t      #                              #\n");  

    printf("\t\t      #         6.查詢個人成績       #\n");  

    printf("\t\t      #                              #\n");  

    printf("\t\t      #         7.查詢本班成績       #\n");  

    printf("\t\t      #                              #\n");  

    printf("\t\t      #         8.查詢全校成績       #\n");  

    printf("\t\t      #                              #\n");  

    printf("\t\t      #         9.退出管理系統       #\n");  

    printf("\t\t      #                              #\n");  

    printf("\t\t      # # # # # # # # # # # # # # # # #\n\n");  

    printf("\t\t       請輸入指令:(1-9) ");  

}  

//構造節點函數

Node* new_node(Node* uu)  

{  

    uu = (Node*)malloc(sizeof(Node));  

    uu->next = NULL;  

    return uu;  

}  

//添加學生信息

void Add()  

{  

//新建一個節點；

    u = new_node(u);  

    printf("\n請輸入您要加入的學生的信息:\n");  

    printf("\n姓名: ");  

    scanf("%s",u->name);  

    printf("\n班級: ");  

    scanf("%s",u->classs);  

    printf("\n學號: ");  

    scanf("%s",u->number);  

    printf("\n語文、數學、英語、物理、化學成績: ");  

    scanf("%d%d%d",&u->score.chinese,&u->score.math,&u->score.english,&u->score.physics,&u->score.chemistry);  

//計算總成績；

    u->score.sum = u->score.chinese + u->score.math + u->score.english + u->score.physics + u->score.chemistry;  

//采用頭插法將新節點的尾指針指向第二個節點(掰開）

    u->next = head->next;  

//將新節點放在頭節點后面；

    head->next = u;  

    printf("\n--->添加成功!\n");  

}  

//根據學號修改信息

//和查找函數一樣，依次從第二個節點開始遍歷，如果找到這更新

void Mod()  

{  

    n = 0;  

    printf("\n請輸入您要修改的學號: ");  

    scanf("%s",num);  

    for(u = head; u != NULL;u = u->next)  

    {  

        if(strcmp(u->number,num) == 0)  

        {  

            n = 1;  

            printf("\n請輸入新的語文、數學、英語、物理、化學成績: ");  

            scanf("%d%d%d",&u->score.chinese,&u->score.math,&u->score.english,&u->score.physics,&u->score.chemistry);  

            u->score.sum = u->score.chinese + u->score.math + u->score.english + u->score.physics + u->score.chemistry;  

            printf("\n--->修改成功!\n");  

            break;  

        }  

    }  

    if(!n)  

        printf("\n--->沒有這個學生的信息!\n");  

}  

//根據學號刪除學生信息，

//從頭節點開始遍歷，如果找到這刪除此節點；

void Del()  

{  

    n = 0;  

    printf("\n請輸入您要刪除的學生的學號: ");  

    scanf("%s",num);  

    for(u = head; u != NULL;u = u->next)  

    {  

        if(strcmp(u->number,num) == 0)  

        {  

            n = 1;  

            p->next = u->next;  

            free(u);  

            printf("\n--->刪除成功!\n");  

            break;  

        }  

        p = u;  

    }  

    if(!n)  

        printf("\n--->沒有這個學生的信息!\n");  

}  

void Sort()  

{  

    int i,j;  

//記錄學生總數；

    n = 0;  

    for(u = head->next; u != NULL;u = u->next)  

        n++;  

//采用冒泡法對各個節點按班級升序和總成績降序排列

    for(i=1;i<=n;i++)  

    {  

        u = head;  

        for(j=0;j<n-i;j++)  

        {  

            p = u->next;  

            q = p->next;  

            if(strcmp(p->classs,q->classs) > 0 || strcmp(p->classs,q->classs) == 0 && p->score.sum < q->score.sum)  

            {  

                u->next = q;  

                p->next = q->next;  

                q->next = p;  

            }  

            u = u->next;  

        }  

    }  

}  

//按學號查找某一學生成績；

void Que_One()  

{  

//標志變量，記錄是否查找成功；

    n = 0;  

    printf("\n請輸入您要查詢的學生的學號: ");  

    scanf("%s",num);  

//從第二個節點開始遍歷，直到最后一個節點為止；

    for(u = head->next; u != NULL;u = u->next)  

    {  

//如果當前節點學號與要查找學號一致這輸出此學生信息；

        if(strcmp(u->number,num) == 0)  

        {  

            n = 1;  

            printf("\n");  

            puts("班級       姓名          語文  數學  英語 物理 化學總成績");  

            printf("%-11s%-15s",u->classs,u->name);  

            printf("%-6d%-6d%-6d%-6d\n",u->score.chinese,u->score.math,u->score.english,u->score.physics,u->score.chemistry,u->score.sum);  

            break;  

        }  

    }  

    if(!n)  

        printf("\n--->沒有這個學生的信息!\n");  

}  

void Analyze_Sco(Node *uu)  

{  

//對查找到的節點進行求各科平均成績

//求優秀率及格率；

    C += uu->score.chinese;  

    M += uu->score.math;  

    E += uu->score.english;  

    D += uu->score.physics; 

    F += uu->score.chemistry; 

    if(uu->score.chinese >= 60)  

        Cj++;  

    if(uu->score.chinese >= 90)  

        Cy++;  

    if(uu->score.math >= 60)  

        Mj++;  

    if(uu->score.math >= 90)  

        My++;  

    if(uu->score.english >= 60)  

        Ej++;  

    if(uu->score.english >= 90)  

        Ey++;  

     if(uu->score.physics >= 60)  

        Dj++;  

    if(uu->score.physics >= 90)  

        Dy++;  

     if(uu->score.chemistry >= 60)  

        Fj++;  

    if(uu->score.chemistry >= 90)  

        Fy++;  

}  

//打印各科平均成績及格率優秀率

void Print_Sco()  

{  

    printf("語文平均成績: %-6.2f, 及格率: %%%-6.2f , 優秀率: %%%-6.2f.\n\n",(float)C/n,(float)100*Cj/n,(float)100*Cy/n);  

    printf("數學平均成績: %-6.2f, 及格率: %%%-6.2f , 優秀率: %%%-6.2f.\n\n",(float)M/n,(float)100*Mj/n,(float)100*My/n);  

    printf("英語平均成績: %-6.2f, 及格率: %%%-6.2f , 優秀率: %%%-6.2f.\n\n",(float)E/n,(float)100*Ej/n,(float)100*Ey/n);  

    printf("物理平均成績: %-6.2f, 及格率: %%%-6.2f , 優秀率: %%%-6.2f.\n\n",(float)D/n,(float)100*Dj/n,(float)100*Dy/n);

    printf("化學平均成績: %-6.2f, 及格率: %%%-6.2f , 優秀率: %%%-6.2f.\n\n",(float)F/n,(float)100*Fj/n,(float)100*Fy/n);

}  

//查找某一班級所以學生的信息；

void Que_Cla()  

{  

//對鏈表節點排序；

    Sort();  

    n = C = M = E = D = F = Cj = Cy = Mj = My = Ej = Ey = Dj = Dy = Fj = Fy = 0;  

    printf("\n請輸入您要查詢的班級: ");  

    scanf("%s",num);  

    printf("\n");  

    for(u = head->next; u != NULL;u = u->next)  

    {  

//不是該班的學生則跳過；

        if(strcmp(u->classs,num))  

            continue;  

//如果是第一個學生則打印頭信息

        if(!n)  

            puts("學號       姓名          語文  數學  英語 物理 化學總成績");  

        n++;  

        printf("%-11s%-15s",u->number,u->name);  

        printf("%-6d%-6d%-6d%-d\n",u->score.chinese,u->score.math,u->score.english,u->score.physics,u->score.chemistry,u->score.sum);  

        Analyze_Sco(u);  

    }  

    if(!n)  

    {  

        printf("沒有這個班級的學生信息!\n");  

        return ;  

    }  

//打印該班級學生的各個成績的特征值；

    printf("\n該班共有學生 %d 人.\n\n",n);  

    Print_Sco();  

}  

//打印全校所以學生的信息

//具體情況同打印班級學生信息；

void Que_All()  

{  

    Sort();  

   n = C = M = E = D = F = Cj = Cy = Mj = My = Ej = Ey = Dj = Dy = Fj = Fy = 0;   

    printf("\n");  

    if(head->next == NULL)  

    {  

        printf("--->沒有學生信息!\n");  

        return ;  

    }  

    puts("班級        學號        姓名          語文  數學  英語 物理 化學 總成績");  

    for(u = head->next; u != NULL;u = u->next)  

    {  

        n++;  

        printf("%-12s%-12s%-15s",u->classs,u->number,u->name);  

        printf("%-6d%-6d%-6d%-d\n",u->score.chinese,u->score.math,u->score.english,u->score.physics,u->score.chemistry,u->score.sum);  

        Analyze_Sco(u);  

    }  

    printf("\n全校共有學生 %d 人.\n\n",n);  

    Print_Sco();  

}  

//保存文件；

void Save()  

{  

    char c;  

    printf("\n確認保存？(Y/N): ");  

    scanf("%*c%c",&c);  

    if(c == 'N')  

        return ;  

    FILE *fp;  

    if((fp=fopen("C:\\data.txt","w"))==NULL)  

    {  

        printf("\n--->無法打開文件\n");  

        return ;  

    }  

//寫入數據表頭信息；

    fputs("班級       學號       姓名          語文  數學  英語 物理 化學 總成績",fp);  

    if(head->next != NULL)  

        fputs("\n",fp);  

//從頭節點開始依次寫入文件；

    for(u = head->next; u != NULL;u = u->next)  

    {  

        fprintf(fp,"%-11s%-11s%-15s",u->classs,u->number,u->name);  

        fprintf(fp,"%-6d%-6d%-6d%-d",u->score.chinese,u->score.math,u->score.english,u->score.physics,u->score.chemistry,u->score.sum);  

        if(u->next != NULL)  

            fprintf(fp,"\n");  

    }  

    fclose(fp);  

    printf("\n--->成績成功存入C:\\\\data.txt中\n");  

}  

//讀取文件；

void Open()  

{  

    printf("\n請把數據放到目錄C:\\\\data.txt中,按任意鍵確認.\n");  

    getch();  

    FILE *fp; 

//從c盤根目錄下讀取文件；

    if((fp=fopen("C:\\data.txt","r"))==NULL)  

    {  

        printf("\n--->沒有找到文件!\n");  

        return ;  

    }  

    char tmp[100];  

//讀取65個菜單頭字符存入tem字符數組中；

    fgets(tmp,66,fp);  

//讀到文件結尾處跳出循環；

    while(!feof(fp))  

    {  

        u = new_node(u);  

        fscanf(fp,"%s%s%s",u->classs,u->number,u->name);  

        fscanf(fp,"%d%d%d%d",&u->score.chinese,&u->score.math,&u->score.english,&u->score.physics,&u->score.chemistry,&u->score.sum);

//頭插法建立鏈表；

        u->next = head->next;  

        head->next = u;  

    }  

    printf("\n--->成績讀入成功!\n");  

    fclose(fp);  

}  

//退出程序

void Exi()  

{  

    char c;  

    printf("\n確定退出？(Y/N): ");  

    scanf("%*c%c",&c);  

    if(c == 'N')  

        return ;  

//打印結束語；

    system("cls");  

    printf("\n\n");  

    printf("\t\t\t     %c %c %c %c %c %c %c %c %c\n",4,4,4,4,4,4,4,4,4);  

    printf("\t\t\t     %c 謝謝使用 %c\n",4,4);  

    printf("\t\t\t     %c %c %c %c %c %c %c %c %c\n",4,4,4,4,4,4,4,4,4);  

    printf("\t\t\t                          Thank you!\n\n\n");  

    exit(0);  

}  

int main()  

{  

//存儲指令的變量

    int orz;  

//設置系統文本顏色

    system("color 7C");  

//新建一個學生信息頭節點；

    head = new_node(head);  

    while(1)  

    {  

//顯示菜單、

        Welcome();  

//接收用戶命令、

        scanf("%d",&orz);  

//調用系統函數清屏；

        system("cls");  

        switch(orz)  

        {  

//根據指令進入相應菜單選項

            case 1:Open();break;  

            case 2:Save();break;  

            case 3:Add();break;  

            case 4:Mod();break;  

            case 5:Del();break;  

            case 6:Que_One();break;  

            case 7:Que_Cla();break;  

            case 8:Que_All();break;  

            case 9:Exi();break;  

            default :printf("\n--->無效的指令!\n");  

        }  

        printf("\n"); 

//執行系統函數

        system("pause");  

        system("cls");  

    }  

    return 0;  

}

     雖然此次上機時間只有短短兩個星期但從中確實學到了不少知識。數據結構可以說是計算機里一門基礎課程，但我覺得我們一低定要把基礎學扎實，然而這次短短的上機幫我又重新鞏固了C語言知識，讓我的水平又一部的提高。數據結構這是一門純屬于設計的科目，它需用把理論變為上機調試。它對我們來說具有一定的難度。它是其它編程語言的一門基本學科。

     通過本次實驗我對鏈表有了更深的了解，對鏈表的插刪操作、遍歷、查找等基本上掌握了。

     同時，通過自己數次的調試、修改也搞懂了許多以前比較模糊的知識點，比如這次的界面是復制 過來的，其中很多語句經過同學的講解都理解了。但這次實驗也有很多不盡人意的地方，比如，只是稍微改編了一點點的地方，很多大的地方都沒改；還有就是本次博客我原來打算加上各 函數的簡單流程圖，但是由于我處理圖形方面還比較不熟練，所以這次博文不太令人滿意，我將在以后多學習同學優秀的地方．也會在以后的學習過程中要盡量考慮周全，使程序更有實用價值，提高 編程能力。

     該程序是經過學生信息管理系統修改而來，把學生學號、姓名、班級、成績，改成語文、數學、英語、物理、化學等即可，只是稍微改了一點點細節就能變成與原來完全不同的程序，所以編程并不是死的，是很靈活的。