C語言的指針、鏈表的原理

一、指針

 1、運用指針

   什么是指針？什么是內(nèi)存地址？什么叫做指針的取值？指針是一個存儲計算機內(nèi)存地址的變量。從指針指向的內(nèi)存讀取數(shù)據(jù)稱作指針的取值。指針可以指向某些具體類型的變量地址，例如int、long和double。指針也可以是void類型、NULL指針和未初始化指針。

   根據(jù)出現(xiàn)的位置不同，操作符 * 既可以用來聲明一個指針變量，也可以用作指針的取值。當(dāng)用在聲明一個變量時，*表示這里聲明了一個指針。其它情況用到*表示指針的取值。&是地址操作符，用來引用一個內(nèi)存地址。通過在變量名字前使用&操作符，我們可以得到該變量的內(nèi)存地址。

例如：

#include<stdio.h>

int main()

{

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

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

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

   int deref =*ptr;  // 對指針進(jìn)行取值，打印存儲在指針地址中的內(nèi)容

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

   第2行，我們通過*操作符聲明了一個int指針。接著我們聲明了一個int變量并賦值為1。然后我們用int變量的地址初始化我們的int指針。接下來對int指針取值，用變量的內(nèi)存地址初始化int指針。最終，我們打印輸出變量值，內(nèi)容為1。

   第6行的&val是一個引用。在val變量聲明并初始化內(nèi)存之后，通過在變量名之前使用地址操作符&我們可以直接引用變量的內(nèi)存地址。

   第8行，我們再一次使用*操作符來對該指針取值，可直接獲得指針指向的內(nèi)存地址中的數(shù)據(jù)。由于指針聲明的類型是int，所以取到的值是指針指向的內(nèi)存地址存儲的int值。

   這里可以把指針、引用和值的關(guān)系類比為信封、郵箱地址和房子。一個指針就好像是一個信封，我們可以在上面填寫郵寄地址。一個引用（地址）就像是一個郵件地址，它是實際的地址。取值就像是地址對應(yīng)的房子。我們可以把信封上的地址擦掉，寫上另外一個我們想要的地址，但這個行為對房子沒有任何影響。

  2、指針和數(shù)組

    C語言的數(shù)組表示一段連續(xù)的內(nèi)存空間，用來存儲多個特定類型的對象。與之相反，指針用來存儲單個內(nèi)存地址。數(shù)組和指針不是同一種結(jié)構(gòu)因此不可以互相轉(zhuǎn)換。而數(shù)組變量指向了數(shù)組的第一個元素的內(nèi)存地址。

例如：

#include<stdio.h>

int main()

{

         int myarray[4] = {1,2,3,0};

    int *ptr = myarray;

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

    ptr++;

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

    ptr++;

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

    ptr++;

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

}

總結(jié)：

指向指針的指針，可以這樣理解，首先指向指針的指針可以把他看成一種特殊的變量，既然是變量就可以存儲不同的元素，比如×××變量int a，a可以存儲2,3,4這種普通的整型數(shù)據(jù)，只要將值付給a就行了，但指向指針的指針?biāo)娴脑乇容^特殊，存放的元素一般是存放地址的指針變量，比如我有三個指針變量，int *p1,*p2,*p3,那么我可以定義一個特殊的變量 int **p,我可以將p1的地址付給p,也可以將p2的地址付給p.比如p=&p1,(類似于int a,int *t,t=&a),那么p就代表了他所指向的變量p1或者p2的地址，而p所指向的變量是一個指針變量，*p代表著這個指針變量里面的值（注意值實際上是一個地址），**p代表著它所指向的指針變量的內(nèi)容(地址)所指向的存儲單元的內(nèi)容（數(shù)值）。

二、鏈表

   鏈表是一種數(shù)據(jù)結(jié)構(gòu) ，其最大的的好處就是能夠為數(shù)據(jù)分配動態(tài)內(nèi)存，就不用像一開始那樣先為系統(tǒng)分配一個都不知道夠不夠用的空間來存貯學(xué)生的信息。

   鏈表，首先可以細(xì)分為一小塊一小塊的結(jié)構(gòu)體變量，這一小塊一小塊的結(jié)構(gòu)體變量在鏈表中是首尾相連的顧名思義 就像一條鐵鏈一樣 而這每一小塊的結(jié)構(gòu)體變量中又可以從大方向地分成兩個部分， 其中一個部分就是——涵蓋著該結(jié)構(gòu)體變量里的所有信息，另一個部分就是鏈接每塊結(jié)構(gòu)體變量的部分——指針。

例如：

typedefstruct node

{

char name[20];

struct node *link;

}stud;

   這樣就定義了一個單鏈表的結(jié)構(gòu)，其中char name[20]是一個用來存儲姓名的字符型數(shù)組，指針*link是一個用來存儲其直接后繼的指針。定義好了鏈表的結(jié)構(gòu)之后，只要在程序運行的時候在數(shù)據(jù)域中存儲適當(dāng)?shù)臄?shù)據(jù)，如有后繼結(jié)點，則把鏈域指向其直接后繼，若沒有，則置為NULL。

三、指針和數(shù)組的區(qū)別

  1.聲明的區(qū)別

   指針：exterenint * x; 

   數(shù)組：externint[] y[];

  2.指針是保存數(shù)據(jù)的地址。

   數(shù)組是保存數(shù)據(jù)。

  3.指針是用于的動態(tài)的數(shù)據(jù)結(jié)構(gòu)。

   數(shù)組是用于儲存固定的數(shù)目且數(shù)據(jù)類型相同的數(shù)據(jù)結(jié)構(gòu)。

   數(shù)組一經(jīng)定義，其基址和大小便固定了，在該數(shù)組的有效使用范圍內(nèi)是不可變的；

   但是指針則具有很強的動態(tài)特征，可以動態(tài)地指向任一該類型（定義決定）變量，這也就決定了它 有更大的靈活性。

  4.數(shù)組是開辟一塊連續(xù)的內(nèi)存空間,數(shù)組本身的標(biāo)示符代表整個數(shù)組。

   指針則是只分配一個指針大小的內(nèi)存,并可把它的值指向某個有效的內(nèi)存空間。

  5.指針是一個變量，可以被賦值，變量的值是另外一個變量的地址。那么，既然指針是變量，那么指    針必然有自己的存儲空間，只不過是該存儲空間內(nèi)的值是一個地址值，而不是別的內(nèi)容。

數(shù)組名僅僅是一個符號，不是變量，不可以被賦值，它沒有自己的存儲空間。

  6.運算速度上的差異。一般來說，用指針要快些，因為在實際的運算中，總是把數(shù)組下標(biāo)表示通過存儲映象函數(shù)轉(zhuǎn)換為指針表示，按其地址訪問內(nèi)存，這種轉(zhuǎn)換要進(jìn)行乘法和加法的運算。

  7.數(shù)組具有較好的可讀性，指針具有更強的靈活性。一般，對某些多維數(shù)組中非連續(xù)的元素的隨機訪問用下標(biāo)表示比較方便，當(dāng)按遞增（減）順序訪問數(shù)組時，使用指針快捷而且方便。

  8.訪問方式：指針是間接訪問，首先取得指針的內(nèi)容作為地址，再去該地址訪問數(shù)據(jù)；

數(shù)組是直接訪問，數(shù)組名即是地址。

四、學(xué)生姓名管理系統(tǒng)

#include <stdio.h> 

#include <conio.h> 

#include <string.h> 

#include <stdlib.h>

#define N 3

typedef struct node

{

   charname[20];

   struct node*link;

}stud;

stud * creat(int n) /*建立單鏈表的函數(shù)*/

{

   stud*p,*h,*s;

   int i;

   if((h=(stud*)malloc(sizeof(stud)))==NULL)

   {

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

      exit(0);

   }

  h->name[0]='\0';

  h->link=NULL;

   p=h;

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

   {

     if((s=(stud *) malloc(sizeof(stud)))==NULL)

     {

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

        exit(0);

     }

    p->link=s;

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

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

    s->link=NULL;

     p=s;

   }

   return(h);

}

stud * search(stud *h,char *x) /*查找函數(shù)*/

{

   stud *p;

   char *y;

   p=h->link;

  while(p!=NULL)

   {

    y=p->name;

    if(strcmp(y,x)==0)

      return(p);

     elsep=p->link;

   }

   if(p==NULL)

     printf("沒有查找到該數(shù)據(jù)!");

}

stud * search3(stud *h,char*x)

/*另一個查找函數(shù)，返回的是上一個查找函數(shù)的直接前驅(qū)結(jié)點的指針，

h為表頭指針，x為指向要查找的姓名的指針

其實此函數(shù)的算法與上面的查找算法是一樣的，只是多了一個指針s，并且s總是指向指針p所指向的結(jié)點的直接前驅(qū)，

結(jié)果返回s即是要查找的結(jié)點的前一個結(jié)點*/

{

   stud *p,*s;

   char *y;

   p=h->link;

   s=h;

  while(p!=NULL)

   {

    y=p->name;

    if(strcmp(y,x)==0)

      return(s);

     else

     {

      p=p->link;

       s=s->link;

     }

   }

   if(p==NULL)

   printf("沒有查找到該數(shù)據(jù)!");

}

void insert(stud *p) /*插入函數(shù)，在指針p后插入*/

{

   charstuname[20];

   stud *s; /*指針s是保存新結(jié)點地址的*/

   if((s= (stud*) malloc(sizeof(stud)))==NULL)

   {

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

     exit(0);

   }

   printf("請輸入你要插入的人的姓名:");

  scanf("%s",stuname);

  strcpy(s->name,stuname); /*把指針stuname所指向的數(shù)組元素拷貝給新結(jié)點的數(shù)據(jù)域*/

  s->link=p->link; /*把新結(jié)點的鏈域指向原來p結(jié)點的后繼結(jié)點*/

   p->link=s;/*p結(jié)點的鏈域指向新結(jié)點*/

}

void del(stud *x,stud *y) /*刪除函數(shù)，其中y為要刪除的結(jié)點的指針，x為要刪除的結(jié)點的前一個結(jié)點的指針*/

{

  stud *s;

  s=y;

 x->link=y->link;

  free(s);

}

void print(stud *h)

{

   stud *p;

   p=h->link;

   printf("數(shù)據(jù)信息為：\n");

  while(p!=NULL)

   {

    printf("%s \n",&*(p->name));

    p=p->link;

   }

}

void quit()

{

  exit(0);

}

void menu(void)

{

   system("cls");

   printf("\t\t\t單鏈表C語言實現(xiàn)實例\n");

   printf("\t\t|----------------|\n");

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

   printf("\t\t| [1] 建 立 新 表 |\n");

   printf("\t\t| [2] 查 找 數(shù) 據(jù) |\n");

   printf("\t\t| [3] 插 入 數(shù) 據(jù) |\n");

   printf("\t\t| [4] 刪 除 數(shù) 據(jù) |\n");

   printf("\t\t| [5] 打 印 數(shù) 據(jù) |\n");

   printf("\t\t| [6] 退 出 |\n");

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

   printf("\t\t| 如未建立新表，請先建立！ |\n");

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

   printf("\t\t|----------------|\n");

   printf("\t\t 請輸入你的選項(1-6):");

}

main()

{

    int choose;

    stud*head,*searchpoint,*forepoint;

    charfullname[20];

    while(1)

    {

      menu();

     scanf("%d",&choose);

     switch(choose)

      {

        case 1:

          head=creat(N);

          break;

        case 2:

                      printf("輸入你所要查找的人的姓名:");

          scanf("%s",fullname);

          searchpoint=search(head,fullname);

          printf("你所查找的人的姓名為:%s",*&searchpoint->name);

          printf("\n按回車鍵回到主菜單。");

          getchar();getchar();

          break;

        case 3:printf("輸入你要在哪個人后面插入:");

          scanf("%s",fullname);

          searchpoint=search(head,fullname);

          printf("你所查找的人的姓名為:%s",*&searchpoint->name);

          insert(searchpoint);

          print(head);

          printf("\n按回車鍵回到主菜單。");

          getchar();getchar();

          break;

        case 4:

                      print(head);

          printf("\n輸入你所要刪除的人的姓名:");

          scanf("%s",fullname);

          searchpoint=search(head,fullname);

          forepoint=search3(head,fullname);

          del(forepoint,searchpoint);

          break;

        case 5:

                      print(head);

          printf("\n按回車鍵回到主菜單。");

          getchar();getchar();

          break;

        case6:quit();

          break;

        default:

                      printf("你輸入了非法字符!按回車鍵回到主菜單。");

          system("cls");

           menu();

           getchar();

      }

   }

}