Chinaunix首页 | 论坛 | 博客
  • 博客访问: 34105
  • 博文数量: 11
  • 博客积分: 355
  • 博客等级: 二等列兵
  • 技术积分: 160
  • 用 户 组: 普通用户
  • 注册时间: 2011-05-07 18:18
文章分类
文章存档

2012年(11)

分类: LINUX

2012-05-14 22:02:27

面试常会考到链表和C库函数的操作,特地整理下了链表的常用函数,以供参考:
一.链表
链表定义如下:
为了程序的可读性,LinkList表示链表头节点指针,用于表示一个链表,pNode表示节点指针

点击(此处)折叠或打开

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<conio.h>
  4.   
  5. typedef struct Node
  6. {
  7.     int data;
  8.     struct Node *next;
  9. }Node,*LinkList,*pNode;
  10. //为了简单起见,我们讲链表值保存到一个数组中,这样链表操作后可以显而易见的看到运行结果是否正确.
  11. int LinkListData[10] = {0,1,2,3,4,5,6,7,8,9};
另外我们创建的链表是带头结点的链表,即单链表的首元结点(存放第一个数据元素的结点)之前附设一个头结点(数据域什么都不放),称之为带头结点的单链表,反之就是不带头结点的单链表。

1.创建链表
(1)顺序创建链表
p是临时节点指针,指向最后一个节点.增加一个节点时实际上就是在链表尾部插入一个新节点.

点击(此处)折叠或打开

  1. LinkList CreateListSequence(int num)
  2. {
  3.     pNode p,pHead,pEnd;
  4.     int i;
  5.     if(!(p = pHead = (LinkList)malloc(sizeof(Node))))
  6.     {
  7.         return NULL;
  8.     }
  9.     p->next = pHead->next = NULL;
  10.     for(i=0;i<num;i )
  11.     {
  12.         if(pEnd = ((LinkList)malloc(sizeof(Node))))
  13.         {
  14.             pEnd->data = LinkListData[i];
  15.             pEnd->next = p->next;
  16.             p->next = pEnd;
  17.             p = pEnd;
  18.         }
  19.     }
  20.     return pHead;
  21. }
(2)逆序创建链表
逆序创建链表时就是将新的节点(pNew)插入到Head节点之后.

点击(此处)折叠或打开

  1. LinkList CreateListInverse(int num)
  2. {
  3.     LinkList pHead,pNew;
  4.     int i;
  5.       
  6.     if(!(pHead=(LinkList)malloc(sizeof(Node))))
  7.     {
  8.         return NULL;
  9.     }
  10.     pHead->next = NULL;
  11.     for(i=0;i<num;i )
  12.     {
  13.         if(pNew=(LinkList)malloc(sizeof(Node)))
  14.         {
  15.             pNew->data = LinkListData[i];
  16.             pNew->next = pHead->next;
  17.             pHead->next = pNew;
  18.         }
  19.     }
  20.     return pHead;
  21. }
2.获取某个指定结点的值

点击(此处)折叠或打开

  1. int GetElement(LinkList list,int location)
  2. {
  3.     int i = 0;
  4.     pNode point = list->next;
  5.     while(point && i<location)
  6.     {
  7.         point = point->next;
  8.         i ;
  9.     }
  10.     if(!point || i > location)
  11.         return 0;
  12.     return point->data;
  13. }
3.插入元素

点击(此处)折叠或打开

  1. int ListInsert(LinkList list,int location,int arg)
  2. {
  3.     pNode point=list->next,node;
  4.     int i=1;
  5.     while(i<location)
  6.     {
  7.         point = point->next;
  8.         i ;
  9.     }
  10.     if(!point || (i > location))
  11.     {
  12.         printf("/nInsert operatoin failed");
  13.         return 0;
  14.     }
  15.     if(!(node =(LinkList)malloc(sizeof(Node))))
  16.         return 0;
  17.     node->data = arg;
  18.     node->next = point->next;
  19.     point->next = node;
  20.       
  21.     return 1;
  22. }
4.删除元素

点击(此处)折叠或打开

  1. void ListDelete(LinkList list,int location)
  2. {
  3.     LinkList point = list->next;
  4.     int i = 1;
  5.     while(i < location)
  6.     {
  7.         point = point->next;
  8.         list = list->next;
  9.         i ;
  10.     }
  11.     if(!point || (i > location))
  12.     {
  13.         printf("/nDelete operation failed!/n");
  14.         return;
  15.     }
  16.     list->next = point->next;
  17.     free(point);
  18. }
5.反序链表
最简单就是前插法,将头结点摘下来,然后采用前插法依次插入,例如:
初始:      head   ->   1   ->   2   ->   3 
第一步:   head 
第二步:   head   ->   1 
第三步:   head   ->   2   ->   1 
第四步:   head   ->   3   ->   2   -> 1 

点击(此处)折叠或打开

  1. LinkList ReverseLinkList(LinkList pHead)
  2. {
  3.     pNode p = pHead-> next;
  4.       
  5.     pHead->next = NULL;
  6.       
  7.     while(p){
  8.         pNode q=p;
  9.         p = p-> next;
  10.         q->next = pHead-> next;
  11.         pHead->next = q;
  12.     }
  13.       
  14.     return pHead;
  15. }
6.找出链表中间节点
采用两个节点指针,一个一次移动2个节点,一个一次移动一个节点,这样只需偏历一次链表就可以找到中间节点了.

点击(此处)折叠或打开

  1. Node* find_midlist(LinkList pHead)
  2. {
  3.     pNode p1, p2;
  4.     if(pHead == NULL || pHead->next == NULL)
  5.         return pHead;
  6.         //链表有头结点,如无头结点,则为p1 = p2 = pHead->next
  7.     p1 = p2 = pHead->next;
  8.     while (1)
  9.     {
  10.         if (p2->next != NULL && p2->next->next != NULL)
  11.         {
  12.             p2 = p2->next->next;
  13.               
  14.             p1 = p1->next;
  15.         }
  16.         else
  17.         {
  18.             break;
  19.         }
  20.     }
  21.     return p1;
  22. }
7.判断一个单链表是否有环
这道题是《C专家编程》中的题了.这里采用的算法是一个指针一次走一步,另一个一次走两步,如果链表有环,那么这两个指针一定会相遇.

点击(此处)折叠或打开

  1. int is_looplist (LinkList pHead)
  2. {
  3.     pNode p1, p2;
  4.       
  5.     p1 = p2 = pHead;
  6.       
  7.     if (pHead == NULL || pHead->next == NULL)
  8.         return 0;
  9.     while (p2->next != NULL && p2->next->next != NULL)
  10.     {
  11.         p1 = p1->next;
  12.         p2 = p2->next->next;
  13.           
  14.         if (p1 == p2)
  15.            return 1;
  16.     }
  17.     return 0;
  18. }

阅读(1167) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~