ITPub博客
首页 博客 专栏 学院 社区 IT新媒体评选
发博

首页 > 应用开发 > IT综合 > 数据结构：链表的初始化插入和删除2.3.1

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

原创 IT综合 作者：gaopengtttt 时间：2016-09-14 21:27:56 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.  ************************************************************************/

  9. #include<iostream>
  10. #include<stdio.h>
  11. #include<stdlib.h>
  12. #include<string.h>
  13. #define INITSIZE 10

  15. typedef unsigned int uint;
  16. typedef int Etype;

  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;


  26. void initsqlist(SQLIST* inlist)
  27. {

  29.         inlist->elem = (Etype* )malloc(sizeof(Etype)*INITSIZE + 1);
  30.         inlist->length = 0;
  31.         inlist->m_size = INITSIZE; //maxsize
  32. }


  35. void initsqlinsert(SQLIST* inlist,Etype ielem,uint postion) //insert elem before postion
  36. {

  38.         int i;
  39.         Etype* newbase;
  40.         if(postion > inlist->length + 1 || postion < 1)
  41.         {

  43.                 printf("line table must continuous or postion must>0!\n");
  44.                 exit(1);
  45.         }

  47.         if(inlist->length + 1 >= inlist->m_size ) //if memory small will give more memory
  48.         {

  50.                 if(!(newbase =(Etype* )realloc(inlist->elem,(inlist->length+INITSIZE)* sizeof(Etype)+1)))
  51.                 {

  53.                         printf("mem alloc failed!\n");
  54.                         exit(2);
  55.                 }
  56.                 inlist->elem = newbase;
  57.                 inlist->m_size = inlist->m_size+INITSIZE;
  58.         }

  60.         for(i=0;i<(inlist->length-postion+2);i++) //every elem houyi
  61.         {

  63.                 *(inlist->elem+inlist->length+1-i) = * (inlist->elem+inlist->length-i);
  64.         }
  65.         *(inlist->elem+inlist->length+1-i) = ielem; //give value
  66.         inlist->length =inlist->length+1;
  67. }

  69. void delsqldel(SQLIST* inlist,uint postion) //delete elem of postion
  70. {

  72.         int i;
  73.         if((postion > inlist->length) ||(postion <1))
  74.         {

  76.                 printf("give postion is must large than 1 and less than current length\n");
  77.         }

  79.         for(i=0;i<(inlist->length-postion) ;i++)
  80.         {

  82.                 *(inlist->elem+postion+i) = *(inlist->elem+postion+i+1);
  83.         }
  84.         inlist->length =inlist->length-1;
  85. }

  87. void view(SQLIST* inlist)
  88. {

  90.         int i;
  91.         if(inlist->length ==0 )
  92.         {

  94.                 printf("init data arrary! no data found!\n");
  95.                 exit(3);
  96.         }
  97.         for(i=0;i<inlist->length;i++)
  98.         {

  100.                 printf("node:%d values is:%d data length:%d max_size:%d \n",i,*(inlist->elem+i),inlist->length,inlist->m_size);
  101.         }
  102. }


点击(此处)折叠或打开

  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;

  9. typedef struct node
  10. {
  11.         datatype data;
  12.         struct node *next;
  13. } Node,*Nodep;

  15. typedef struct hnode
  16. {
  17.         int clenth;
  18.         Nodep headp;
  19. } Hnode,*Hnodep;


  22. typedef struct sqlist
  23. {
  24.         Etype* elem; //pointer of sqlist base address
  25.         uint length; //current length of elem
  26.         uint m_size; //
  27. } SQLIST;

  29. void initchain(Hnodep hnode,int n)
  30. {
  31.         Nodep p;
  32.         int i;
  33.         hnode->clenth = 0;
  34.         hnode->headp = (Nodep)malloc(sizeof(Node));
  35.         hnode->headp->next = NULL;
  36.         hnode->headp->data = 0;
  37.         (hnode->clenth)++;
  38.         for(i=(n-1);i>0;--i)
  39.         {
  40.                 p = (Nodep)malloc(sizeof(Node));
  41.                 p->next = hnode->headp->next;
  42.                 hnode->headp->next = p;
  43.                 p->data = 0;
  44.                 (hnode->clenth)++;
  45.         }
  46. }


  49. void initchain(Hnodep hnode,const SQLIST* sqdata)
  50. {
  51.         Nodep p;
  52.         int i;
  53.         int t=1;
  54.         int sqlen = sqdata->length;
  55.         hnode->clenth = 0;
  56.         hnode->headp = (Nodep)malloc(sizeof(Node));
  57.         hnode->headp->next = NULL;
  58.         hnode->headp->data = *(sqdata->elem);
  59.         (hnode->clenth)++;
  60.         sqlen--;
  61.         for(i=sqlen;i>0;--i)//every time insert elem after first elem and before seconed elem
  62.         {
  63.                 p = (Nodep)malloc(sizeof(Node));
  64.                 p->next = hnode->headp->next;
  65.                 hnode->headp->next = p;
  66.                 p->data = *(sqdata->elem+t);
  67.                 (hnode->clenth)++;
  68.                 t++;
  69.         }
  70. }


  73. void viewchain(Hnodep hnode)
  74. {
  75.         int i=1;
  76.         Nodep p;
  77.         int max_len;
  78.         p = hnode->headp;
  79.         max_len = hnode->clenth;

  81.         printf("Max chain length is:%d\n",max_len);
  82.         do
  83.         {
  84.                 printf("node:%d values is: %d\n",i,p->data);
  85.                 i++;

  87.         }while(p=p->next);
  88. }

  90. void getelem(Hnodep hnode,int postion)
  91. {
  92.         int i=0;
  93.         Nodep p;
  94.         if(postion > hnode->clenth || postion ==0 )
  95.         {
  96.                 printf("postion large than lenth or poastion = 0\n");
  97.                 exit(4);
  98.         }
  99.         p = hnode->headp;

  101.         while(i<postion-1)
  102.         {
  103.                 i++;
  104.                 p = p->next;
  105.         }

  107.         printf("node %d values is %d\n",i+1,p->data);

  109. }


  112. Nodep getelemp(const Hnodep hnode,int postion) //insert one elem after postion
  113. {
  114.         int i=0;
  115.         Nodep p;
  116.         if(postion > hnode->clenth || postion ==0 )
  117.         {
  118.                 printf("postion large than lenth or poastion = 0\n");
  119.                 exit(5);
  120.         }
  121.         p = hnode->headp;

  123.         while(i<postion-1)
  124.         {
  125.                 i++;
  126.                 p = p->next;
  127.         }

  129.         return p;

  131. }

  133. void addnode(Nodep inode,int postion,Hnodep hnode)//insert one elem after postion
  134. {
  135.         Nodep p;
  136.         p = getelemp(hnode,postion);
  137.         if(!p->next) //end elem?
  138.         {
  139.                 p->next = inode;
  140.                 inode->next = NULL;
  141.         }
  142.         else
  143.         {
  144.                 inode->next = p->next;
  145.                 p->next = inode;
  146.         }
  147.         hnode->clenth++;
  148. }

  150. void delnode(int postion,Hnodep hnode) //delete elem at give postion
  151. {
  152.         Nodep p1; //delete postion-1 p
  153.         Nodep p2; //delete postion p

  155.         if(postion == 1)
  156.         {
  157.                 p2 = hnode->headp->next;
  158.                 hnode->headp->next = hnode->headp->next->next;
  159.                 free(p2);
  160.         }
  161.         else
  162.         {
  163.                 p1=getelemp(hnode,postion-1);//find before delete node postion
  164.                 p2 = p1->next;
  165.                 p1->next = p1->next->next;
  166.                 free(p2);
  167.         }
  168.         hnode->clenth--;
  169. }


点击(此处)折叠或打开

  1. main 函数：
  2. #include<iostream>
  3. #include<stdio.h>
  4. #include<stdlib.h>


  7. typedef unsigned int uint;
  8. typedef int Etype;
  9. typedef int datatype;

  11. typedef struct node
  12. {

  14.         datatype data;
  15.         struct node *next;
  16. } Node,*Nodep;

  18. typedef struct hnode
  19. {

  21.         int clenth;
  22.         Nodep headp;
  23. } Hnode,*Hnodep;


  26. typedef struct sqlist
  27. {

  29.         Etype* elem; //pointer of sqlist base address
  30.         uint length; //current length of elem
  31.         uint m_size; //
  32. } SQLIST;

  34. void initchain(Hnodep hnode,int n);
  35. void initchain(Hnodep hnode,const SQLIST* sqdata);
  36. void viewchain(Hnodep hnode);
  37. void view(SQLIST* inlist);
  38. void delsqldel(SQLIST* inlist,uint postion);
  39. void initsqlist(SQLIST* inlist);
  40. void initsqlinsert(SQLIST* inlist,Etype ielem,uint postion);
  41. void getelem(Hnodep hnode,int postion);
  42. void addnode(Nodep inode,int postion,const Hnodep hnode);
  43. void delnode(int postion,Hnodep hnode);


  46. int main(void)
  47. {
  48.         SQLIST a;
  49.         Hnode chd1;
  50.         Nodep newnode = (Nodep)malloc(sizeof(Node));
  51.         newnode->data=50;
  52.         newnode->next=NULL;
  53.         initsqlist(&a);
  54.         printf("insert 5 values use seq mode\n");
  55.         initsqlinsert(&a,5,1);
  56.         initsqlinsert(&a,10,1);
  57.         initsqlinsert(&a,15,1);
  58.         initsqlinsert(&a,20,1);
  59.         initsqlinsert(&a,25,1);
  60.         view(&a);
  61.         printf("\n\ninit chain use seq arrary\n");
  62.         initchain(&chd1,&a);
  63.         viewchain(&chd1);
  64.         printf("\n\nview one node at postion 3\n");
  65.         getelem(&chd1,3);
  66.     printf("\n\nadd one node after node 2\n");
  67.         addnode(newnode,2,&chd1);
  68.         viewchain(&chd1);
  69.         printf("\n\nadd one node at postion 2\n");
  70.         delnode(2,&chd1);
  71.         viewchain(&chd1);
  72.         return 0;
  73. }


编译：
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博客 ” ，链接：https://blog.itpub.net/7728585/viewspace-2125007/ ，如需转载，请注明出处，否则将追究法律责任。

0
0
上一篇： 数据结构：线性表的顺序实现2.2
下一篇： 数据结构：双向链表
请登录后发表评论 登录
全部评论
gaopengtttt
专家姓名：高鹏
wxh gp_22389860 公众号 MySQL学习 书籍 深入理解MySQL主从原理

注册时间：2021-06-07

  • 博文量
    868
  • 访问量
    3495563

最新文章

支持我们 作者招募 用户协议 FAQ Contact Us

北京盛拓优讯信息技术有限公司. 版权所有  京ICP备16024965号-8 北京市公安局海淀分局网监中心备案编号：11010802021510 niuxiaotong@pcpop.com 17352615567 未成年人举报专区

广播电视节目制作经营许可证(京) 字第1234号 中国互联网协会会员

违法和不良信息举报电话:18101376593