[关闭]
@52fhy 2016-01-14T21:01:29.000000Z 字数 6618 阅读 333

指针与链表

C

*是指针，**是指向指针的指针，而指针就是地址，一个*是指向一个变量的地址，而 ** 则是指向 * 的地址，存放的是 * 的地址。指针是常量。

  1. #include<stdio.h>
  2. void main(){
  3.     int **p,*j,i=100;
  4.     j=&i; //等价于 int *j = &i;
  5.     p=&j; //等价于 int **p = &j;
  6.     printf("%d\n",**p); //100
  7. }

即：

  1. p = &j;
  2. *p = j = &i;
  3. **p = i = 100;
  5. //p是地址(&j),j是地址($i)。*用来取地址里的值，

指针可以理解为地址。

  1. int a[5] = {1,2,3,4,5};
  2. int *p = a; //c语言里a就代表数组a的首地址。这里定义指针p指向的数组a类型是int型。即指针p里存储的是数组a的首地址。
  3. char **point = &p; //等价于char **point; ponit = &p; //指针作为常量，本身也有地址。point是指向指针的指针。

链表

  1. #include "stdio.h"
  2. #include <stdlib.h>
  3. #include "string.h"
  5. typedef int elemType ; //定义int别名elemType
  7. typedef struct Node{    /* 定义单链表结点类型 */
  8.     elemType element;
  9.     struct Node *next;
  10. }Node; //定义该结构体别名Node
  12. /* 1.初始化线性表，即置单链表的表头指针为空 */
  14. //注意形参是指针的指针
  15. void initList(Node **pNode)
  16. {
  17.     *pNode = NULL;
  18.     printf("initList函数执行，初始化成功\n");
  19. }
  21. int main()
  22. {
  23.     Node *pList=NULL;
  24.     int length = 0;
  26.     elemType posElem;
  28.     //pList本身是地址变量，这里&pList相当于: Node **p;p= &pList。传入的是指针的指针
  29.     initList(&pList);       //链表初始化
  30.  }

创建线性表

  1. /* 2.创建线性表，此函数输入负数终止读取数据*/
  2. Node *creatList(Node *pHead)
  3. {
  4.     Node *p1;
  5.     Node *p2;
  7.     p1=p2=(Node *)malloc(sizeof(Node)); //申请新节点
  8.     if(p1 == NULL || p2 ==NULL)
  9.     {
  10.         printf("内存分配失败\n");
  11.         exit(0);
  12.     }
  13.     memset(p1,0,sizeof(Node));
  15.     scanf("%d",&p1->element);    //输入新节点
  16.     p1->next = NULL;         //新节点的指针置为空
  17.     while(p1->element > 0)        //输入的值大于0则继续，直到输入的值为负
  18.     {
  19.         if(pHead == NULL)       //空表，接入表头
  20.         {
  21.             pHead = p1;
  22.         }
  23.         else               
  24.         {
  25.             p2->next = p1;       //非空表，接入表尾
  26.         }
  27.         p2 = p1;
  28.         p1=(Node *)malloc(sizeof(Node));    //再重申请一个节点
  29.         if(p1 == NULL || p2 ==NULL)
  30.         {
  31.         printf("内存分配失败\n");
  32.         exit(0);
  33.         }
  34.         memset(p1,0,sizeof(Node));
  35.         scanf("%d",&p1->element);
  36.         p1->next = NULL;
  37.     }
  38.     printf("creatList函数执行，链表创建成功\n");
  39.     return pHead;           //返回链表的头指针
  40. }

附录

  1. #include "stdafx.h"
  2. #include "stdio.h"
  3. #include <stdlib.h>
  4. #include "string.h"
  6. typedef int elemType ;
  8. /************************************************************************/
  9. /*             以下是关于线性表链接存储（单链表）操作的18种算法        */
  11. /* 1.初始化线性表，即置单链表的表头指针为空 */
  12. /* 2.创建线性表，此函数输入负数终止读取数据*/
  13. /* 3.打印链表，链表的遍历*/
  14. /* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
  15. /* 5.返回单链表的长度 */
  16. /* 6.检查单链表是否为空，若为空则返回１，否则返回０ */
  17. /* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
  18. /* 8.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
  19. /* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
  20. /* 10.向单链表的表头插入一个元素 */
  21. /* 11.向单链表的末尾添加一个元素 */
  22. /* 12.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */
  23. /* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */
  24. /* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */
  25. /* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */
  26. /* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */
  27. /* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
  28. /* 18.交换2个元素的位置 */
  29. /* 19.将线性表进行快速排序 */
  32. /************************************************************************/
  33. typedef struct Node{    /* 定义单链表结点类型 */
  34.     elemType element;
  35.     struct Node *next;
  36. }Node;
  39. /* 1.初始化线性表，即置单链表的表头指针为空 */
  40. void initList(Node **pNode)
  41. {
  42.     *pNode = NULL;
  43.     printf("initList函数执行，初始化成功\n");
  44. }
  46. /* 2.创建线性表，此函数输入负数终止读取数据*/
  47. Node *creatList(Node *pHead)
  48. {
  49.     Node *p1;
  50.     Node *p2;
  52.     p1=p2=(Node *)malloc(sizeof(Node)); //申请新节点
  53.     if(p1 == NULL || p2 ==NULL)
  54.     {
  55.         printf("内存分配失败\n");
  56.         exit(0);
  57.     }
  58.     memset(p1,0,sizeof(Node));
  60.     scanf("%d",&p1->element);    //输入新节点
  61.     p1->next = NULL;         //新节点的指针置为空
  62.     while(p1->element > 0)        //输入的值大于0则继续，直到输入的值为负
  63.     {
  64.         if(pHead == NULL)       //空表，接入表头
  65.         {
  66.             pHead = p1;
  67.         }
  68.         else               
  69.         {
  70.             p2->next = p1;       //非空表，接入表尾
  71.         }
  72.         p2 = p1;
  73.         p1=(Node *)malloc(sizeof(Node));    //再重申请一个节点
  74.         if(p1 == NULL || p2 ==NULL)
  75.         {
  76.         printf("内存分配失败\n");
  77.         exit(0);
  78.         }
  79.         memset(p1,0,sizeof(Node));
  80.         scanf("%d",&p1->element);
  81.         p1->next = NULL;
  82.     }
  83.     printf("creatList函数执行，链表创建成功\n");
  84.     return pHead;           //返回链表的头指针
  85. }
  87. /* 3.打印链表，链表的遍历*/
  88. void printList(Node *pHead)
  89. {
  90.     if(NULL == pHead)   //链表为空
  91.     {
  92.         printf("PrintList函数执行，链表为空\n");
  93.     }
  94.     else
  95.     {
  96.         while(NULL != pHead)
  97.         {
  98.             printf("%d ",pHead->element);
  99.             pHead = pHead->next;
  100.         }
  101.         printf("\n");
  102.     }
  103. }
  105. /* 4.清除线性表L中的所有元素，即释放单链表L中所有的结点，使之成为一个空表 */
  106. void clearList(Node *pHead)
  107. {
  108.     Node *pNext;            //定义一个与pHead相邻节点
  110.     if(pHead == NULL)
  111.     {
  112.         printf("clearList函数执行，链表为空\n");
  113.         return;
  114.     }
  115.     while(pHead->next != NULL)
  116.     {
  117.         pNext = pHead->next;//保存下一结点的指针
  118.         free(pHead);
  119.         pHead = pNext;      //表头下移
  120.     }
  121.     printf("clearList函数执行，链表已经清除\n");
  122. }
  124. /* 5.返回单链表的长度 */
  125. int sizeList(Node *pHead)
  126. {
  127.     int size = 0;
  129.     while(pHead != NULL)
  130.     {
  131.         size++;         //遍历链表size大小比链表的实际长度小1
  132.         pHead = pHead->next;
  133.     }
  134.     printf("sizeList函数执行，链表长度 %d \n",size);
  135.     return size;    //链表的实际长度
  136. }
  138. /* 6.检查单链表是否为空，若为空则返回１，否则返回０ */
  139. int isEmptyList(Node *pHead)
  140. {
  141.     if(pHead == NULL)
  142.     {
  143.         printf("isEmptyList函数执行，链表为空\n");
  144.         return 1;
  145.     }
  146.     printf("isEmptyList函数执行，链表非空\n");
  148.     return 0;
  149. }
  151. /* 7.返回单链表中第pos个结点中的元素，若pos超出范围，则停止程序运行 */
  152. elemType getElement(Node *pHead, int pos)
  153. {
  154.     int i=0;
  156.     if(pos < 1)
  157.     {
  158.         printf("getElement函数执行，pos值非法\n");
  159.         return 0;
  160.     }
  161.     if(pHead == NULL)
  162.     {
  163.         printf("getElement函数执行，链表为空\n");
  164.         return 0;
  165.         //exit(1);
  166.     }
  167.     while(pHead !=NULL)
  168.     {
  169.         ++i;
  170.         if(i == pos)
  171.         {
  172.             break;
  173.         }
  174.         pHead = pHead->next; //移到下一结点
  175.     }
  176.     if(i < pos)                  //链表长度不足则退出
  177.     {
  178.         printf("getElement函数执行，pos值超出链表长度\n");
  179.         return 0;
  180.     }
  182.     return pHead->element;
  183. }
  185. /* 8.从单链表中查找具有给定值x的第一个元素，若查找成功则返回该结点data域的存储地址，否则返回NULL */
  186. elemType *getElemAddr(Node *pHead, elemType x)
  187. {
  188.     if(NULL == pHead)
  189.     {
  190.         printf("getElemAddr函数执行，链表为空\n");
  191.         return NULL;
  192.     }
  193.     if(x < 0)
  194.     {
  195.         printf("getElemAddr函数执行，给定值X不合法\n");
  196.         return NULL;
  197.     }
  198.     while((pHead->element != x) && (NULL != pHead->next)) //判断是否到链表末尾，以及是否存在所要找的元素
  199.     {
  200.         pHead = pHead->next;
  201.     }
  202.     if((pHead->element != x) && (pHead != NULL))
  203.     {
  204.         printf("getElemAddr函数执行，在链表中未找到x值\n");
  205.         return NULL;
  206.     }
  207.     if(pHead->element == x)
  208.     {
  209.         printf("getElemAddr函数执行，元素 %d 的地址为 0x%x\n",x,&(pHead->element));
  210.     }
  212.     return &(pHead->element);//返回元素的地址
  213. }
  215. /* 9.把单链表中第pos个结点的值修改为x的值，若修改成功返回１，否则返回０ */
  216. int modifyElem(Node *pNode,int pos,elemType x)
  217. {
  218.     Node *pHead;
  219.     pHead = pNode;
  220.     int i = 0;
  222.     if(NULL == pHead)
  223.     {
  224.         printf("modifyElem函数执行，链表为空\n");
  225.     }
  226.     if(pos < 1)
  227.     {
  228.         printf("modifyElem函数执行，pos值非法\n");
  229.         return 0;
  230.     }
  231.     while(pHead !=NULL)
  232.     {
  233.         ++i;
  234.         if(i == pos)
  235.         {
  236.             break;
  237.         }
  238.         pHead = pHead->next; //移到下一结点
  239.     }
  240.     if(i < pos)                  //链表长度不足则退出
  241.     {
  242.         printf("modifyElem函数执行，pos值超出链表长度\n");
  243.         return 0;
  244.     }
  245.     pNode = pHead;
  246.     pNode->element = x;
  247.     printf("modifyElem函数执行\n");
  249.     return 1;
  250. }
  252. /* 10.向单链表的表头插入一个元素 */
  253. int insertHeadList(Node **pNode,elemType insertElem)
  254. {
  255.     Node *pInsert;
  256.     pInsert = (Node *)malloc(sizeof(Node));
  257.     memset(pInsert,0,sizeof(Node));
  258.     pInsert->element = insertElem;
  259.     pInsert->next = *pNode;
  260.     *pNode = pInsert;
  261.     printf("insertHeadList函数执行，向表头插入元素成功\n");
  263.     return 1;
  264. }
  266. /* 11.向单链表的末尾添加一个元素 */
  267. int insertLastList(Node **pNode,elemType insertElem)
  268. {
  269.     Node *pInsert;
  270.     Node *pHead;
  271.     Node *pTmp; //定义一个临时链表用来存放第一个节点
  273.     pHead = *pNode;
  274.     pTmp = pHead;
  275.     pInsert = (Node *)malloc(sizeof(Node)); //申请一个新节点
  276.     memset(pInsert,0,sizeof(Node));
  277.     pInsert->element = insertElem;
  279.     while(pHead->next != NULL)
  280.     {
  281.         pHead = pHead->next;
  282.     }
  283.     pHead->next = pInsert;   //将链表末尾节点的下一结点指向新添加的节点
  284.     *pNode = pTmp;
  285.     printf("insertLastList函数执行，向表尾插入元素成功\n");
  287.     return 1;
  288. }
  290. /* 12.向单链表中第pos个结点位置插入元素为x的结点，若插入成功返回１，否则返回０ */
  293. /* 13.向有序单链表中插入元素x结点，使得插入后仍然有序 */
  294. /* 14.从单链表中删除表头结点，并把该结点的值返回，若删除失败则停止程序运行 */
  295. /* 15.从单链表中删除表尾结点并返回它的值，若删除失败则停止程序运行 */
  296. /* 16.从单链表中删除第pos个结点并返回它的值，若删除失败则停止程序运行 */
  297. /* 17.从单链表中删除值为x的第一个结点，若删除成功则返回1,否则返回0 */
  298. /* 18.交换2个元素的位置 */
  299. /* 19.将线性表进行快速排序 */
  301. /******************************************************************/
  302. int main()
  303. {
  304.     Node *pList=NULL;
  305.     int length = 0;
  307.     elemType posElem;
  309.     initList(&pList);       //链表初始化
  310.     printList(pList);       //遍历链表，打印链表
  312.     pList=creatList(pList); //创建链表
  313.     printList(pList);
  315.     sizeList(pList);        //链表的长度
  316.     printList(pList);
  318.     isEmptyList(pList);     //判断链表是否为空链表
  320.     posElem = getElement(pList,3);  //获取第三个元素，如果元素不足3个，则返回0
  321.     printf("getElement函数执行，位置 3 中的元素为 %d\n",posElem);   
  322.     printList(pList);
  324.     getElemAddr(pList,5);   //获得元素5的地址
  326.     modifyElem(pList,4,1);  //将链表中位置4上的元素修改为1
  327.     printList(pList);
  329.     insertHeadList(&pList,5);   //表头插入元素12
  330.     printList(pList);
  332.     insertLastList(&pList,10);  //表尾插入元素10
  333.     printList(pList);
  335.     clearList(pList);       //清空链表
  336.     system("pause");
  338. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注