AI 助理
备案控制台
开发者社区 开发与运维 文章 正文

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

2016-09-14 843
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 前面我们已经说了线性表的顺序实现， http://blog.itpub.net/7728585/viewspace-2124937/ 下面我们将讨论一下线性表的链表实现。
前面我们已经说了线性表的顺序实现，
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 


文章标签：
C++
C语言
数据库
关键词：
数据结构链表
数据结构初始化
链表数据结构
数据结构链表初始化
链表初始化
重庆八怪
目录
相关文章
XIAZHI
|
26天前
|
存储 算法 Perl
数据结构实验之链表
本实验旨在掌握线性表中元素的前驱、后续概念及链表的建立、插入、删除等算法，并分析时间复杂度，理解链表特点。实验内容包括循环链表应用（约瑟夫回环问题）、删除单链表中重复节点及双向循环链表的设计与实现。通过编程实践，加深对链表数据结构的理解和应用能力。
XIAZHI
52 4
龙大吉
|
19天前
|
存储 缓存 算法
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中，数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式，强调了合理选择数据结构的重要性，并通过案例分析展示了其在实际项目中的应用，旨在帮助读者提升编程能力。
龙大吉
42 5
ephemerals__
|
1月前
|
存储 C语言
【数据结构】手把手教你单链表（c语言）（附源码）
本文介绍了单链表的基本概念、结构定义及其实现方法。单链表是一种内存地址不连续但逻辑顺序连续的数据结构，每个节点包含数据域和指针域。文章详细讲解了单链表的常见操作，如头插、尾插、头删、尾删、查找、指定位置插入和删除等，并提供了完整的C语言代码示例。通过学习单链表，可以更好地理解数据结构的底层逻辑，提高编程能力。
ephemerals__
73 4
肾透侧视攻城狮
|
1月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解（9）【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子；这都学不会；能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛？！！！
肾透侧视攻城狮
25 2
肾透侧视攻城狮
|
1月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的；不然别给我家鸽鸽丢脸好嘛？】
数据结构之单双链表按位、值查找；[前后]插入；删除指定节点；求表长、静态链表等代码及具体思路详解步骤；举例说明、注意点及常见报错问题所对应的解决方法
肾透侧视攻城狮
36 2
XIAZHI
|
26天前
|
算法
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能，支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构，并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示，系统在处理小规模购物车时表现良好，但在大规模购物车操作下可能存在性能瓶颈。
XIAZHI
43 0
ephemerals__
|
1月前
|
C语言
【数据结构】双向带头循环链表（c语言）（附源码）
本文介绍了双向带头循环链表的概念和实现。双向带头循环链表具有三个关键点：双向、带头和循环。与单链表相比，它的头插、尾插、头删、尾删等操作的时间复杂度均为O(1)，提高了运行效率。文章详细讲解了链表的结构定义、方法声明和实现，包括创建新节点、初始化、打印、判断是否为空、插入和删除节点等操作。最后提供了完整的代码示例。
ephemerals__
52 0
白子寰
|
2月前
|
存储
[数据结构] -- 双向循环链表
[数据结构] -- 双向循环链表
白子寰
25 0
阿客不是客
|
2月前
|
存储
探索数据结构：便捷的双向链表
探索数据结构：便捷的双向链表
阿客不是客
22 0
阿客不是客
|
2月前
|
存储
探索数据结构：单链表的实践和应用
探索数据结构：单链表的实践和应用
阿客不是客
73 0