标签: 链表

我这些天在学习数据结构，发现了一些问题。闲话少叙，先上代码（参考教材：数据结构-c语言，耿国华编著，有删改） #include   typedef struct node//结构体，单链表 { char data; struct node * next;   }node,* linklist;   int  countfromtail(linklist l)//记录长度 { /*以下是原来错误的。红色字体是改进过的*/ //linklist l_copy; //l_copy = l; //p = l_copy-next; p = l-next; node *p; int count = 0;   while (p!= NULL) { p= p-next; count++; } return count; }   node * findlinklist(linklist l, char q)//按值查找 { node *r; r = l-next; while (l-next != NULL) { if (r-data != q) { r = r-next; } else break; } return r; } linklist creatfromtail()//链表创建 { linklist l; node *r, *s; int flag = 1; char c; l = (node *)malloc(sizeof(node)); l-next = NULL; r = l; while (flag) { c = getchar();   if (c != 'a') { s = (node *)malloc(sizeof(node)); s-data = c; r-next = s; r = s; } else { flag = 0; r-next = NULL; } } return l; }     int main() { int m=0; char q='b'; linklist l; node *z; l=creatfromtail(); m = countfromtail(l); printf("the length of list is %d\n", m); z = findlinklist(l, q);     printf("the charecter you want to find is %c\n", z-data); return 0; }     以上代码实现的链表的创建，对元素计数，按值查找三个功能，代码是比较简陋，但是还是比较完整的。这个代码是有问题的，可以思考一下， 好了，先说一下整个流程。从主函数main说起，第一步：定义，初始化；第二步：创建一个链表；第三步：计数，记录链表长度，并打印出来；第四步：查找一个字符，本例是查找‘b'，打印出来查找的字符。 结果：创建和记录长度都正常，查找字符这一步导致控制台无响应。 我想说的第一个问题，第三步 调用countfromtail(linklist l) 以后，输出这是没有问题的。来到第四步，直接使用参数l，直接使用指针问题是：l-next指向的不是第一个，而是最后一个！！！导致第四步l-next=NULL,结果导致并不能输出’b'。 为什么出现上述问题？原因是：调用函数是值传递，将链表l传递给函数时，它的下一个节点l-next在经过第三步记录长度后已经变成了Null，而不是按照我们的意愿从第一个结点开始。为了验证这一点，在第三步复制一份指针l，对l_copy操作，以后的第四步就不会影响对l的影响。果然，这次运行符合预期。 第二个问题：链表存储的数据是char类型的，遇到‘a'就停止，把a当作结束符，这一步的确不是很好，但我说的不是这点。我想说在字符输入的时候我错误的以为回车不会当作链表元素，我是每输入一个字符敲一个回车，导致当输入n个字符时候显示长度却是2*n-1。   总结：1、指针是个坏蛋，近两天时间就是因为它，却慢慢喜欢它咯，真是磨人的小妖精。 2、关于参数传递，我觉得学的很好了，却还是栽了跟头。 努力吧，刚刚开始，路还很长！  

  双链表 3.1 双链表的结点结构 #define  NULL  ((void*)0)  typedef  struct  dnode {       int   datanode;       struct dnode  *prior;       struct dnode  *next; }dlinklist; 3.2 插入运算  int DLinkListInsert(dlinklist *head, int i, int x) {         int j=0;         dlinklist *p;         dlinklist *s;           p=head;         while(ji-1 p-next !=NULL)         {             p=p-next;             j++;         }       if(j!=i-1)       {             return 0;       }       p=p-next; //p指向 要插入数据的后一个结点  but为什么是后一个结点，前一个结点不行吗?       s=(dlinklist *) malloc(sizeof(dlinklist));       s-datanode=x;       s-prior = p-prior;       p-prior-next =s;       p-prior=s;       s-next= p;       return 1; }   3.3 删除运算 int DLinkListDelet(dlinklist * head, int i) {         int j=0;         dlinklist *p;           p=head;         while(ji p-next !=NULL)         {             p=p-next;    //p指向要删除结点             j++;         }       if(j!=i|| i==0)   //带头结点的不能删去头结点       {             return 0;       }       p-prior-next=p-next;       p-next-prior=p-prior;       return 1; } Ucos-II 中线性表的用法 就以任务控制链表为例进行描述：   OSTCBFreeList 及 OSTCBTbl 的定义 OS_TCB   xdata   *data   OSTCBFreeList;  OS_TCB   xdata   *data   OSTCBList; OS_TCB   OSTCBTbl ; 在 OSInit() 中有对 OSTCBFreelist 的初始化操作     OS_TCB    *ptcb1;     OS_TCB    *ptcb2;   ptcb1 = OSTCBTbl ;// 查找任务控制块列表 (0) 的对应地址   ptcb2 = OSTCBTbl ;   for (i = 0; i (OS_MAX_TASKS + OS_N_SYS_TASKS - 1); i++)  {        ptcb1-OSTCBNext = ptcb2;  ptcb1++;  ptcb2++;  } ptcb1-OSTCBNext = (OS_TCB *)0;                           OSTCBFreeList    = OSTCBTbl ; 当创建任务时调用 OS_TCBInit() ，此函数对 OSTCB 进行操作，它从 OSTCBFreeList 单链表最前面取出一个结点， 给结构体中各参数赋值后前插到双链表 OSTCBList 。 当删除任务时，再将结点从 OSTCBList 删除，并放回 OSTCBFreeList 。 在函数 OSTimeTick() 中扫描链表对结点结构体中的 .OSTCBDly 减一操作。 其他的链表还有： OSEventFreeList OSQFreeList OSFlagFreeList OSMemFreeList

  单链表 2.1 单链表的结点结构 typedef struct node {       int  nodedata;       struct node  *next; }linklist; 2.2建立单链表 (1) 头插法  linklist * Creatlist_Frontinsert() { char ch,i;       linklist *head,*p;       head=NULL;        //head指向空       ch=getchar();     //获得第一个字符       for(i=0;i10;i++)       {             p= (linklist *)malloc(sizeof(linklist));     //给新链表的node分配空间             p-nodedata=ch;                    //给 .nodedata 赋值             p-next=head;                       //头插法，把P放到head前面             head=p;   //head 再指向P，即上一句中p为头，这一句再把head作为头             ch=getchar();                        //获得每一次的字符       }    return   head;                             //返回头指针 } (2)尾插法  linklist * Creatlist_Endinsert1() {       char ch,i;       linklist *head,*p, *end;       head=NULL;       end=NULL;       ch=getchar();       for(i=0;i10;i++)       {             p= (linklist *)malloc(sizeof(linklist));             p-nodedata=ch;             if(head==NULL)                                {                   head=p;         //如果链表是空的，直接head指向P                              }             else             {                   end-next=p;       //如果链表不是空的，那么尾指针的.next指向P             }       end=p; //尾指针end 指向p,尾指针后移了，因为尾指针始终指向最后一个node             ch=getchar();       }       if(end!=NULL)       {             end-next = NULL;       //非空链表的话尾指针的.next指向NULL。                                             //    空链表本来就指向NULL，就不在重新说明了       }    return   head; } 上面的尾插法有点复杂了，考虑了空和非空链表的情况，如果给链表带一个头结点（实际什么都不干），那么就会简单很多。 (3) 尾插法(带头结点的)  linklist * Creatlist_Endinsert2() {       char ch,i;       linklist *head,*p, *end;         head = (linklist *)malloc(sizeof(linklist));          //申请空间建立头结点       end=head;         //end 初始化指向head       ch=getchar();       for(i=0;i10;i++)       {             p= (linklist *)malloc(sizeof(linklist));             p-nodedata=ch;             end-next = p;             end=p;             ch=getchar();       }       end-next = NULL;       return head; } 2.3 插入运算 int  ListInsert(linklist *head,int i, int x) {       int j=0;       linklist *p;   //用于查找       linklist *s;  //用于指向插入的结点             p=head;       while(ji-1p-next!=NULL)/i-1p-       {             p=p-next; //沿链表逐个扫描，直到i-1 ，P这个时候指向要插入的位置的前一个             j++;       }       if(j!=i-1)        {           return 0;       }         s=(linklist *)malloc(sizeof(linklist));       s-nodedata=x;       s-next=p-next;       p-next = s;       return 1; } 2.4删除运算 int ListDelete(linklist *head,int i) {       int j=0;       linklist *p;   //用于查找       linklist *s;  //用于指向要删除的结点             p=head;       while(ji-1p-next!=NULL)/i-1p-       {             p=p-next; //沿链表逐个扫描，直到i-1 ，P这个时候指向要要删除节点的前一个             j++;       }       if((j!=i-1)||p-next == NULL)        {           return 0;       }         s=p-next;         p-next=s-next;         free(s);       return 1; } 单链表特点：只有后继没有前趋