首页 > 其他分享 >数据结构之线性表

数据结构之线性表

时间：2023-11-10 17:44:07浏览次数：45  
标签：return 线性表 int pos next tmpHead 数据结构 pLink

线性表之顺序存储：

  1 sqlist.h
  2 #ifndef _SQLIST_H
  3 #define _SQLIST_H
  4 
  5 #define    MAX_SIZE 6
  6 typedef struct
  7 {
  8     int data[MAX_SIZE];
  9     int last;
 10 }sqlist,*sqlink;
 11 
 12 void creatList(sqlink L);//建空表
 13 int  getLength(sqlink L);//求表长
 14 int  isEmptyList(sqlink L);//是否为空
 15 int  isFullList(sqlink L);//是否满
 16 void clearList(sqlink L);//清空
 17 int  deleteList(sqlink L, int pos);//删除指定位置的元素
 18 int  getList(sqlink L, int pos);//获得指定位置的值
 19 int  locateList(sqlink L, int data);//找指定元素的位置
 20 int  insertList(sqlink L, int data, int pos);//在指定位置插入元素
 21 void showList(sqlink L);//打印线性表
 22 #endif
 23 
 24 main.c
 25 #include "sqlist.h"
 26 #include <stdlib.h>
 27 #include <stdio.h>
 28 #include <string.h>
 29 
 30 int main()
 31 {
 32     sqlink H = (sqlink)malloc(sizeof(sqlist));
 33     memset(H->data, 0 ,sizeof(H->data));
 34     H->last = -1;
 35     if(H == NULL){
 36         printf("malloc failed\n");
 37     }
 38 
 39     creatList(H);    
 40     showList(H);
 41     
 42     printf("======insert========\n");
 43     insertList(H, 88, 3);
 44     showList(H);
 45     
 46     printf("======delete========\n");
 47     deleteList(H, 2);
 48     showList(H);
 49     
 50     printf("======get date at pos========\n");
 51     int value = getList(H, 4);
 52     printf("value =%d\n", value);
 53     
 54     printf("======get pos of data========\n");
 55     int pos = locateList(H, 88);
 56     printf("position =%d\n", pos);
 57     
 58 }
 59 
 60 sqlist.c
 61 #include "sqlist.h"
 62 #include <stdio.h>
 63 
 64 void creatList(sqlink L)
 65 {
 66     int index = 1;
 67     int tmpdata = 0;
 68     do{
 69         printf("please input %d number:",index);
 70         scanf("%d",&tmpdata);
 71         if(tmpdata != -1){
 72             L->data[index - 1] = tmpdata;
 73             L->last = index - 1;
 74             printf("L->last = %d MAX_SIZE = %d\n",L->last, MAX_SIZE);
 75             index++;                
 76         }            
 77     }while((tmpdata != -1) && (L->last < MAX_SIZE));
 78     
 79     if(L->last >= MAX_SIZE){
 80         printf("list element not enough\n");
 81         L->last = L->last -1;
 82     }
 83 }//建空表
 84 
 85 int  getLength(sqlink L)
 86 {
 87     return L->last + 1;
 88 }//求表长
 89 
 90 int  isEmptyList(sqlink L)
 91 {
 92     if(L->last == -1)
 93         return 1;
 94     else
 95         return 0;
 96 }//是否为空
 97 
 98 int  isFullList(sqlink L)
 99 {
100     if(L->last == MAX_SIZE - 1)
101         return 1;
102     else
103         return 0;
104     
105 }//是否满
106 
107 void  clearList(sqlink L)
108 {
109     L->last = 0;    
110 }//清空
111 
112 int  deleteList(sqlink L, int pos)
113 {
114     if(isEmptyList(L)){
115         printf("this list is empty\n");
116         return 0;
117     }    
118     
119     if((pos < 0) || (pos > MAX_SIZE -1)){
120         printf("delete position not correct\n");
121         return 0;
122     }
123     
124     for(int i = pos; i < getLength(L) -1; i++){
125         L->data[i] = L->data[i+1];
126     }
127     
128     L->last = L->last -1;
129     return 1;
130 }//删除指定位置的元素
131 
132 int  getList(sqlink L, int pos)
133 {
134     if((pos < 0) || (pos > MAX_SIZE -1)){
135         printf("position not correct\n");
136         return 0;
137     }
138     
139     return L->data[pos];    
140 }//获得指定位置的值
141 
142 int  locateList(sqlink L, int data)
143 {
144     if(isEmptyList(L)){
145         printf("this list is empty\n");
146         return 0;
147     }    
148     
149     
150     for(int i = 0; i < getLength(L);i++){
151         if(data == L->data[i])
152             return i;
153     }
154     
155     return -1;
156 }//找指定元素的位置
157 
158 int  insertList(sqlink L, int data, int pos)
159 {
160     if(isFullList(L)){
161         printf("this list is full\n");
162         return 0;
163     }
164     
165     if((pos < 0) || pos >(MAX_SIZE -1)){
166         printf("insert position not correct\n");
167         return 0;
168     }    
169     
170     for(int j = getLength(L)- 1; j >= pos; j--){
171         L->data[j+1] = L->data[j];//j等于pos时，也要往后移
172     }
173     
174     L->data[pos] = data;
175     L->last = L->last +1;
176     
177     return 1;
178 }//在指定位置插入元素
179 
180 void showList(sqlink L)
181 {
182     for(int i = 0; i < getLength(L); i++){
183         printf("output:%d ",L->data[i]);
184     }
185     printf("\n");
186 }//打印线性表

 线性表之链式存储：

  1 linklist.h
  2 #ifndef _LINKLIST_H
  3 #define _LINKLIST_H
  4 
  5 typedef struct node{
  6     int data;
  7     struct node *next;
  8 }linkNode,*pLink;
  9 
 10 void creatLinkFromHead(pLink H);
 11 
 12 void creatLinkFromTail(pLink H); 
 13 
 14 int insertFromHead(pLink H, int value);
 15 
 16 int insertFromTail(pLink H, int value);
 17 
 18 int getLenOfLink(pLink H);
 19 
 20 int insertFromLocate(pLink H, int pos, int value);//在指定位置插入值
 21 
 22 int deleteFromLocate(pLink H, int pos);//删除指定位置的值
 23 
 24 int modifyFromLocate(pLink H, int pos, int value);//修改指定位置的值
 25 
 26 int findValue(pLink H, int pos);//查找位置找值
 27 
 28 int findPos(pLink H, int value);//通过值找位置
 29 
 30 void showLink(pLink H);
 31 
 32 #endif 
 33 
 34 
 35 linklist.c
 36 #include "linklist.h"
 37 #include <stdio.h>
 38 #include <stdlib.h>
 39 
 40 int insertFromHead(pLink H, int value)
 41 {
 42     pLink tmpHead = (pLink)malloc(sizeof(linkNode));
 43     if(tmpHead == NULL){
 44         printf("insertFromHead malloc node failed\n");
 45         return -1;
 46     }
 47     tmpHead->data = value;
 48     if(H->next == NULL){                
 49         tmpHead->next = NULL;    
 50         H->next = tmpHead;            
 51     }else{
 52         tmpHead->next = H->next;    
 53         H->next = tmpHead;
 54     }
 55     
 56     return 0;
 57 }
 58 
 59 void creatLinkFromHead(pLink H)
 60 {
 61     int index = 1;
 62     int value = 0;
 63     if(H == NULL){
 64         printf("head is null\n");
 65         return ;
 66     }
 67     while(1){
 68         printf("请输入第%d个数：",index);
 69         scanf("%d", &value);
 70         if(value == -1){
 71             return;
 72         }else{
 73             insertFromHead(H, value);
 74         }
 75         index++;
 76     }
 77     return ;
 78 }
 79 
 80 int insertFromTail(pLink H, int value)
 81 {
 82     pLink tmpHead = H;
 83     
 84     pLink tmpNode = (pLink)malloc(sizeof(linkNode));
 85     if(tmpNode == NULL){
 86         printf("insertFromTail malloc node failed\n");
 87         return -1;
 88     }
 89     tmpNode->data = value;
 90     tmpNode->next = NULL;
 91     
 92     while(tmpHead->next != NULL){ //找到最后一个节点
 93         tmpHead = tmpHead->next; 
 94     }
 95     
 96     tmpHead->next = tmpNode;
 97     return 0;
 98 }
 99 
100 void creatLinkFromTail(pLink H)
101 {
102     int index = 1;
103     int value = 0;
104     if(H == NULL){
105         printf("head is null\n");
106         return ;
107     }
108     
109     while(1){
110         printf("请输入第%d个数：", index);
111         scanf("%d", &value);
112         if(-1 == value){
113             return ;
114         }else{
115             insertFromTail(H, value);
116         }
117     }
118     return ;
119 }
120 
121 int getLenOfLink(pLink H)
122 {
123     int len = 0;
124     pLink tmpHead = H;
125     while(tmpHead ->next != NULL){
126         len++;
127         tmpHead = tmpHead->next;
128     }
129     
130     return len;
131 }
132 
133 int insertFromLocate(pLink H, int pos, int value)//在指定位置插入值
134 {
135     int locate = 1;
136     pLink tmpHead = H;
137     if((pos < 1) || (pos > getLenOfLink(H))){
138         printf("position is not correct\n");
139         return -1;
140     }
141     
142     pLink tmpNode = (pLink)malloc(sizeof(linkNode));
143     tmpNode->data = value;
144     
145     /*if((pos == 1) && (tmpHead->next != NULL)){ //这种方法插入也可以
146         tmpNode->next = tmpHead->next;
147         tmpHead->next = tmpNode;
148         return 0;
149     }else{
150         while(tmpHead->next != NULL){
151             locate++;
152             tmpHead = tmpHead->next;
153             if(pos == locate){
154                 tmpNode->next = tmpHead->next;
155                 tmpHead->next = tmpNode;
156                 return 0;
157             }
158         }
159     }*/
160 
161     while(tmpHead->next != NULL){
162         if(pos == locate){
163             tmpNode->next = tmpHead->next;
164             tmpHead->next = tmpNode;
165             return 0;
166         }
167         locate++;
168         tmpHead = tmpHead->next;//tmpHead指针指向的节点要在locate的前一个位置，即要定位到所找位置的前一个指针
169     }
170 
171     return -1;
172 }
173 
174 int deleteFromLocate(pLink H, int pos)//删除指定位置的值
175 {
176     int locate = 1;
177     pLink tmpHead = H;
178     if((pos < 1) || (pos > getLenOfLink(H))){
179         printf("position is not correct\n");
180         return -1;
181     }
182     
183     pLink tmpNode = NULL;
184     while(tmpHead->next != NULL){
185         if(pos == locate){
186             tmpNode = tmpHead->next ;
187             tmpHead->next = tmpNode->next;
188             return 0;
189         }
190         locate++;
191         tmpHead = tmpHead->next;
192     }    
193     return -1;
194 }
195 
196 int modifyFromLocate(pLink H, int pos, int value)//修改指定位置的值
197 {
198     int locate = 1;
199     pLink tmpHead = H;
200     if((pos < 1) || (pos > getLenOfLink(H))){
201         printf("position is not correct\n");
202         return -1;
203     }
204     
205     while(tmpHead->next != NULL){
206         if(pos == locate){
207             tmpHead->next->data = value; 
208             return 0;
209         }
210         locate++;
211         tmpHead = tmpHead->next;
212     }    
213     
214     return -1;
215 }
216 
217 
218 int findValue(pLink H, int pos)//查找位置找值
219 {
220     int locate = 1;
221     pLink tmpHead = H;
222     if((pos < 1) || (pos > getLenOfLink(H))){
223         printf("position is not correct\n");
224         return -1;
225     }
226 
227     while(tmpHead->next != NULL){
228         if(pos == locate){
229             return tmpHead->next->data;
230         }
231         locate++;
232         tmpHead = tmpHead->next;
233     }
234     
235     return -1;
236 }
237 
238 int findPos(pLink H, int value)//通过值找位置
239 {
240     int pos = 0;
241     if(H == NULL){
242         printf("link is null\n");
243         return -1;
244     }
245     
246     pLink tmpHead = H;
247     while(tmpHead->next != NULL){
248         pos++;
249         tmpHead = tmpHead->next;
250         
251         if(tmpHead->data == value){
252             return pos;
253         }                
254     }
255     return -1;
256 }
257 
258 //链表的翻转
259 int invertlink(pLink H)
260 {
261     if(H == NULL){
262         printf("this link is null\n");
263         return -1;
264     }
265     
266     pLink tmpHead1 = H->next;
267     pLink tmpHead2 = NULL;
268     
269     pLink tmpHead3 = H;
270     tmpHead3->next = NULL;
271     
272     while(tmpHead1 != NULL){
273         tmpHead1 = tmpHead1->next;
274         tmpHead2 = tmpHead1->next;
275         if(tmpHead3->next == NULL){
276             tmpHead2->next = NULL;
277             tmpHead3->next = tmpHead2;
278         }else{
279             tmpHead2->next = tmpHead3->next;
280             tmpHead3->next = tmpHead2;
281         }
282     }    
283     
284     H = tmpHead3;
285     
286     return 0;
287 }
288 
289 void showLink(pLink H)
290 {
291     if(H == NULL){
292         printf("show link is null\n");
293         return ;
294     }
295     
296     pLink tmpHead = H;
297     while(tmpHead->next != NULL){
298         printf("data = %d\n", tmpHead->next->data);
299         tmpHead = tmpHead->next;
300     }
301     return ;
302 }
303 
304 linklist_main.c
305 #include "linklist.h"
306 #include <stdio.h>
307 #include <stdlib.h>
308 
309 int main()
310 {
311     pLink head = (pLink)malloc(sizeof(linkNode));
312     head->next = NULL;
313     if(head == NULL){
314         printf("malloc failed\n");
315         return -1;
316     }
317     
318     /*creatLinkFromHead(head);    
319     showLink(head);*/
320     
321     creatLinkFromTail(head);    
322     showLink(head);
323 
324     printf("+++++++++++++++++++++++++++++++\n");
325     invertlink(head);
326     showLink(head);
327     
328     printf("+++++++++++++++++++++++++++++++\n");
329     insertFromLocate(head, 5, 88);
330     showLink(head);
331     
332     printf("\n+++++++++++++++++++++++++++++++\n");
333     deleteFromLocate(head, 4);
334     showLink(head);
335     
336     printf("\n+++++++++++++++++++++++++++++++\n");
337     modifyFromLocate(head, 4, 66);
338     showLink(head);
339     
340     printf("所找位置的值%d\n",findValue(head, 4));
341     
342     printf("找2所在的位置%d\n",findPos(head, 2));
343     
344     
345     
346     return 0;
347 }

 

标签：return,线性表,int,pos,next,tmpHead,数据结构,pLink
From： https://www.cnblogs.com/zj-studyrecoding/p/17814047.html

相关文章

  • 数据结构-队列
    一、概念1、队列的定义队列是仅限在一端进行插入，另一端进行删除的线性表。队列又被称为先进先出（FirstInFirstOut）的线性表，简称FIFO。2、队首允许进行元素删除的一端称为队首3、队尾允许进行元素插入的一端称为队尾二、接口1、可写接口（1）数据入队队列的插入操作，叫做入队。它是......
  • 数据结构入门 — 顺序表详解
    前言数据结构入门—顺序表详解关注博主，后期持续更新系列文章文章末尾有源码*****感谢观看，希望对你有所帮助*****文章目录前言一、顺序表1.顺序表是什么2.优缺点二、概念及结构1.静态顺序表2.动态顺序表三、顺序表接口实现（代码演示）1.动态存储结构2.顺序表打印3.顺序表初......
  • 数据结构入门 — 链表详解_双向链表
    前言数据结构入门—双向链表详解*关注博主，后期持续更新系列文章文章末尾有源码*****感谢观看，希望对你有所帮助*****系列文章第一篇：数据结构入门—链表详解_单链表第二篇：数据结构入门—链表详解_双向链表第三篇：数据结构入门—链表详解_循环链表文章目录前言系列文章什......
  • 自己写数据结构
    #include<iostream>#include<array>template<typenameT,size_tS>classArray{private: Tm_data[S];public: constexprintSize()const{ returnS; } T&operator[](intindex){returnm_data[index];} constT&operator[](in......
  • 高级数据结构学习笔记
    0.普适技巧动态开点：节省空间。标记永久化：分块的块标记本质就是这个。可以节省空间。1.区间最值&历史区间最值link2.二维线段树二维区间静态：二维ST表二维前缀动态：二维树状数组二维区间动态：二维线段树例题：LuckandLove、P3157[CQOI2011]动态逆序......
  • 数据结构的两个层次
    逻辑结构：描述数据元素之间的逻辑关系与数据的存储无关，独立于计算机是从具体问题抽象出来的数学模型 2.物理结构（存储结构）数据元素及其关系在计算机存储器中的结构（存储方式）是数据结构在计算机的表示 关系：存储结构是逻辑关系的映象与元素本身的映象逻辑......
  • 考研_数据结构
    绪论1.算法原地工作是指辅助空间不随着数据规模的增大而增大，不是说不需要辅助空间2.栈和队列属于逻辑结构而非存储结构，它们的实现才属于存储结构3.数据元素是数据的基本单位，数据项是数据的最小单位4.程序需要算法和数据结构结合在一起才能实现，仅仅把算法用某种计算机语言来描述......
  • 2008秋季-计算机软件基础- 线性表顺序存储 - 菜单
    /*2008-10-27*//*tod:删除,修改,参考:教材P63-67*/#include<stdio.h>#defineN1typedefstructstudent{charxuehao[10];charxingming[10];intchengji;}S;voidxianshicaidan(){printf("\n1-Initialization.\n");......
  • 2008秋季-计算机软件基础-线性表的顺序存储（顺序表）
    引例：在一维数组中插入和删除元素//在一维数组中插入和删除元素//2008-8-31#include<stdio.h>voidmain(){//在一维数组位置Location处插入EintList[10]={0,1,2,3,4,5};intListLength=6;//表长intE=6;//被插入的元素inti;//循环变量intLocati......
  • 2008秋季-线性表的链式存储（仅单链表）
    /*---------------------------------------------------------Title:单链表Date:September1,2008Fuction:单链表的初始化，创建，插入，删除，查找结点。参考PPT讲稿或者教材2.2.4节.(p56-63)----------------------------------------------------------*/#inclu......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99