1. 首页
  2. IT资讯

数据结构:链表的初始化插入和删除2.3.1

前面我们已经说了线性表的顺序实现,
http://blog.itpub.net/7728585/viewspace-2124937/
下面我们将讨论一下线性表的链表实现。
链表结构使用得非常多,不管是操作系统还是数据库都是使用非常频繁的一种数据结构,
由于其相对灵活的内存使用,并且快速的插入和删除,都是非常有优势的。
这里通过C语言实现5个功能:
1、使用线性表的顺序结构初始化链表结构
2、初始化链表结构为指定的大小
3、获取链表中的指定位置的元素
4、在指定位置后面插入一个元素
5、删除指定位置的元素
先来看一个大概的图,说明是是加NODENEW加入到节点NODE1后面的情况,实际上删除也是类似,具体实现看代码

首先我们需要定义个头结点指向第一个NODE,NODE中有NEXT指针指向下一个结点,在这种结构中,
查看固定元素的时间复杂度最坏也是O(n),而插入一元素时间复杂度为O(1),删除一个元素复杂度也是O(1)
但是我们应该清楚如果要插入指定位置或者删除指定位置的元素首先需要的是查询,那么需要的时间则是他们
相加。来看C语言实现,在整个代码文件中没有使用头文件导致每个文件都需要定义一些需要的定义!同时我
使用了函数重载来实现
1、使用线性表的顺序结构初始化链表结构
2、初始化链表结构为指定的大小
不可避免的引入了一点点C++的知识

点击(此处)折叠或打开

  1. 顺序表实现:
  2. /*************************************************************************
  3.   > File Name: sqlist.cpp
  4.   > Author: gaopeng
  5.   > Mail: gaopp_200217@163.com
  6.   > Created Time: Wed 05 Oct 2016 02:44:35 AM CST
  7.  ************************************************************************/
  8. #include<iostream>
  9. #include<stdio.h>
  10. #include<stdlib.h>
  11. #include<string.h>
  12. #define INITSIZE 10
  13. typedef unsigned int uint;
  14. typedef int Etype;
  15. typedef struct sqlist
  16. {
  17.         Etype* elem; //pointer of sqlist base address
  18.         uint length; //current length of elem
  19.         uint m_size; //
  20. } SQLIST;
  21. void initsqlist(SQLIST* inlist)
  22. {
  23.         inlist>elem = (Etype* )malloc(sizeof(Etype)*INITSIZE + 1);
  24.         inlist>length = 0;
  25.         inlist>m_size = INITSIZE; //maxsize
  26. }
  27. void initsqlinsert(SQLIST* inlist,Etype ielem,uint postion) //insert elem before postion
  28. {
  29.         int i;
  30.         Etype* newbase;
  31.         if(postion > inlist>length + 1 || postion < 1)
  32.         {
  33.                 printf(“line table must continuous or postion must>0!n”);
  34.                 exit(1);
  35.         }
  36.         if(inlist>length + 1 >= inlist>m_size ) //if memory small will give more memory
  37.         {
  38.                 if(!(newbase =(Etype* )realloc(inlist>elem,(inlist>length+INITSIZE)* sizeof(Etype)+1)))
  39.                 {
  40.                         printf(“mem alloc failed!n”);
  41.                         exit(2);
  42.                 }
  43.                 inlist>elem = newbase;
  44.                 inlist>m_size = inlist>m_size+INITSIZE;
  45.         }
  46.         for(i=0;i<(inlist>lengthpostion+2);i++) //every elem houyi
  47.         {
  48.                 *(inlist>elem+inlist>length+1i) = * (inlist>elem+inlist>lengthi);
  49.         }
  50.         *(inlist>elem+inlist>length+1i) = ielem; //give value
  51.         inlist>length =inlist>length+1;
  52. }
  53. void delsqldel(SQLIST* inlist,uint postion) //delete elem of postion
  54. {
  55.         int i;
  56.         if((postion > inlist>length) ||(postion <1))
  57.         {
  58.                 printf(“give postion is must large than 1 and less than current lengthn”);
  59.         }
  60.         for(i=0;i<(inlist>lengthpostion) ;i++)
  61.         {
  62.                 *(inlist>elem+postion+i) = *(inlist>elem+postion+i+1);
  63.         }
  64.         inlist>length =inlist>length1;
  65. }
  66. void view(SQLIST* inlist)
  67. {
  68.         int i;
  69.         if(inlist>length ==0 )
  70.         {
  71.                 printf(“init data arrary! no data found!n”);
  72.                 exit(3);
  73.         }
  74.         for(i=0;i<inlist>length;i++)
  75.         {
  76.                 printf(“node:%d values is:%d data length:%d max_size:%d n”,i,*(inlist>elem+i),inlist>length,inlist>m_size);
  77.         }
  78. }

点击(此处)折叠或打开

  1. 链表实现:
  2. #include<iostream>
  3. #include<stdio.h>
  4. #include <stdlib.h>
  5. typedef int datatype;
  6. typedef int Etype;
  7. typedef unsigned int uint;
  8. typedef struct node
  9. {
  10.         datatype data;
  11.         struct node *next;
  12. } Node,*Nodep;
  13. typedef struct hnode
  14. {
  15.         int clenth;
  16.         Nodep headp;
  17. } Hnode,*Hnodep;
  18. typedef struct sqlist
  19. {
  20.         Etype* elem; //pointer of sqlist base address
  21.         uint length; //current length of elem
  22.         uint m_size; //
  23. } SQLIST;
  24. void initchain(Hnodep hnode,int n)
  25. {
  26.         Nodep p;
  27.         int i;
  28.         hnode>clenth = 0;
  29.         hnode>headp = (Nodep)malloc(sizeof(Node));
  30.         hnode>headp>next = NULL;
  31.         hnode>headp>data = 0;
  32.         (hnode>clenth)++;
  33.         for(i=(n1);i>0;i)
  34.         {
  35.                 p = (Nodep)malloc(sizeof(Node));
  36.                 p>next = hnode>headp>next;
  37.                 hnode>headp>next = p;
  38.                 p>data = 0;
  39.                 (hnode>clenth)++;
  40.         }
  41. }
  42. void initchain(Hnodep hnode,const SQLIST* sqdata)
  43. {
  44.         Nodep p;
  45.         int i;
  46.         int t=1;
  47.         int sqlen = sqdata>length;
  48.         hnode>clenth = 0;
  49.         hnode>headp = (Nodep)malloc(sizeof(Node));
  50.         hnode>headp>next = NULL;
  51.         hnode>headp>data = *(sqdata>elem);
  52.         (hnode>clenth)++;
  53.         sqlen;
  54.         for(i=sqlen;i>0;i)//every time insert elem after first elem and before seconed elem
  55.         {
  56.                 p = (Nodep)malloc(sizeof(Node));
  57.                 p>next = hnode>headp>next;
  58.                 hnode>headp>next = p;
  59.                 p>data = *(sqdata>elem+t);
  60.                 (hnode>clenth)++;
  61.                 t++;
  62.         }
  63. }
  64. void viewchain(Hnodep hnode)
  65. {
  66.         int i=1;
  67.         Nodep p;
  68.         int max_len;
  69.         p = hnode>headp;
  70.         max_len = hnode>clenth;
  71.         printf(“Max chain length is:%dn”,max_len);
  72.         do
  73.         {
  74.                 printf(“node:%d values is: %dn”,i,p>data);
  75.                 i++;
  76.         }while(p=p>next);
  77. }
  78. void getelem(Hnodep hnode,int postion)
  79. {
  80.         int i=0;
  81.         Nodep p;
  82.         if(postion > hnode>clenth || postion ==0 )
  83.         {
  84.                 printf(“postion large than lenth or poastion = 0n”);
  85.                 exit(4);
  86.         }
  87.         p = hnode>headp;
  88.         while(i<postion1)
  89.         {
  90.                 i++;
  91.                 p = p>next;
  92.         }
  93.         printf(“node %d values is %dn”,i+1,p>data);
  94. }
  95. Nodep getelemp(const Hnodep hnode,int postion) //insert one elem after postion
  96. {
  97.         int i=0;
  98.         Nodep p;
  99.         if(postion > hnode>clenth || postion ==0 )
  100.         {
  101.                 printf(“postion large than lenth or poastion = 0n”);
  102.                 exit(5);
  103.         }
  104.         p = hnode>headp;
  105.         while(i<postion1)
  106.         {
  107.                 i++;
  108.                 p = p>next;
  109.         }
  110.         return p;
  111. }
  112. void addnode(Nodep inode,int postion,Hnodep hnode)//insert one elem after postion
  113. {
  114.         Nodep p;
  115.         p = getelemp(hnode,postion);
  116.         if(!p>next) //end elem?
  117.         {
  118.                 p>next = inode;
  119.                 inode>next = NULL;
  120.         }
  121.         else
  122.         {
  123.                 inode>next = p>next;
  124.                 p>next = inode;
  125.         }
  126.         hnode>clenth++;
  127. }
  128. void delnode(int postion,Hnodep hnode) //delete elem at give postion
  129. {
  130.         Nodep p1; //delete postion1 p
  131.         Nodep p2; //delete postion p
  132.         if(postion == 1)
  133.         {
  134.                 p2 = hnode>headp>next;
  135.                 hnode>headp>next = hnode>headp>next>next;
  136.                 free(p2);
  137.         }
  138.         else
  139.         {
  140.                 p1=getelemp(hnode,postion1);//find before delete node postion
  141.                 p2 = p1>next;
  142.                 p1>next = p1>next>next;
  143.                 free(p2);
  144.         }
  145.         hnode>clenth;
  146. }

点击(此处)折叠或打开

  1. main 函数:
  2. #include<iostream>
  3. #include<stdio.h>
  4. #include<stdlib.h>
  5. typedef unsigned int uint;
  6. typedef int Etype;
  7. typedef int datatype;
  8. typedef struct node
  9. {
  10.         datatype data;
  11.         struct node *next;
  12. } Node,*Nodep;
  13. typedef struct hnode
  14. {
  15.         int clenth;
  16.         Nodep headp;
  17. } Hnode,*Hnodep;
  18. typedef struct sqlist
  19. {
  20.         Etype* elem; //pointer of sqlist base address
  21.         uint length; //current length of elem
  22.         uint m_size; //
  23. } SQLIST;
  24. void initchain(Hnodep hnode,int n);
  25. void initchain(Hnodep hnode,const SQLIST* sqdata);
  26. void viewchain(Hnodep hnode);
  27. void view(SQLIST* inlist);
  28. void delsqldel(SQLIST* inlist,uint postion);
  29. void initsqlist(SQLIST* inlist);
  30. void initsqlinsert(SQLIST* inlist,Etype ielem,uint postion);
  31. void getelem(Hnodep hnode,int postion);
  32. void addnode(Nodep inode,int postion,const Hnodep hnode);
  33. void delnode(int postion,Hnodep hnode);
  34. int main(void)
  35. {
  36.         SQLIST a;
  37.         Hnode chd1;
  38.         Nodep newnode = (Nodep)malloc(sizeof(Node));
  39.         newnode>data=50;
  40.         newnode>next=NULL;
  41.         initsqlist(&a);
  42.         printf(“insert 5 values use seq moden”);
  43.         initsqlinsert(&a,5,1);
  44.         initsqlinsert(&a,10,1);
  45.         initsqlinsert(&a,15,1);
  46.         initsqlinsert(&a,20,1);
  47.         initsqlinsert(&a,25,1);
  48.         view(&a);
  49.         printf(“nninit chain use seq arraryn”);
  50.         initchain(&chd1,&a);
  51.         viewchain(&chd1);
  52.         printf(“nnview one node at postion 3n”);
  53.         getelem(&chd1,3);
  54.     printf(“nnadd one node after node 2n”);
  55.         addnode(newnode,2,&chd1);
  56.         viewchain(&chd1);
  57.         printf(“nnadd one node at postion 2n”);
  58.         delnode(2,&chd1);
  59.         viewchain(&chd1);
  60.         return 0;
  61. }

编译:
g++ main.cpp chain.cpp sqlist.cpp  -W
运行:
gaopeng@bogon:~/datas/part2/chain$ ./a.out 
insert 5 values use seq mode
node:0 values is:25 data length:5 max_size:10 
node:1 values is:20 data length:5 max_size:10 
node:2 values is:15 data length:5 max_size:10 
node:3 values is:10 data length:5 max_size:10 
node:4 values is:5 data length:5 max_size:10 

init chain use seq arrary
Max chain length is:5
node:1 values is: 25
node:2 values is: 5
node:3 values is: 10
node:4 values is: 15
node:5 values is: 20

view one node at postion 3
node 3 values is 10

add one node after node 2
Max chain length is:6
node:1 values is: 25
node:2 values is: 5
node:3 values is: 50
node:4 values is: 10
node:5 values is: 15
node:6 values is: 20

add one node at postion 2
Max chain length is:5
node:1 values is: 25
node:2 values is: 50
node:3 values is: 10
node:4 values is: 15
node:5 values is: 20

可以看到我初始化的链表为 25 5 10 15 20 查看第三个元素为 10 在位置2后面插入一个元素50 变为
 25 5 50 10 15 20 删除位置2元素变为了 25  50 10 15 20 

来自 “ ITPUB博客 ” ,链接:http://blog.itpub.net/7728585/viewspace-2125007/,如需转载,请注明出处,否则将追究法律责任。

主题测试文章,只做测试使用。发布者:深沉的少年,转转请注明出处:http://www.cxybcw.com/183859.html

联系我们

13687733322

在线咨询:点击这里给我发消息

邮件:1877088071@qq.com

工作时间:周一至周五,9:30-18:30,节假日休息

QR code