- 微信
- 微博
  
  分享文章到微博
- 复制链接
  
  复制链接到剪贴板

[数据结构] 线性表(顺序结构和链式结构)

开心星人发表于 2022/06/29 23:52:20 2022/06/29

1.2k+ 0 0

【摘要】文章目录顺序存储结构链式存储结构顺序存储结构 //#include <bits/stdc++.h> #include <iostream> #include...

文章目录

- 顺序存储结构
- 链式存储结构

顺序存储结构

//#include <bits/stdc++.h>
#include <iostream>
#include <string>
#define MAXSIZE 100
#define OK 1;
#define ERROR 0;
using namespace std;

typedef int Status;

typedef struct{
    string name;
    string gender;
    int age;
}Student;

typedef struct{
    Student * elem;
    int length;
}SqList;
void menu(){
	cout<<"************************************************"<<endl;
    cout<<"*	1----初始化一个线性表"<<endl;
    cout<<"*	2----销毁线性表"<<endl;
    cout<<"*	3----清空线性表"<<endl;
    cout<<"*	4----判断线性表是否为空"<<endl;
    cout<<"*	5----求线性表长度"<<endl;
    cout<<"*	6----获取线性表指定位置元素"<<endl;
    cout<<"*	7----求前驱"<<endl;
    cout<<"*	8----求后继"<<endl;
    cout<<"*	9----在线性表指定位置插入元素"<<endl;
    cout<<"*	10----删除线性表指定位置元素"<<endl;
    cout<<"*	11----显示线性表"<<endl;
    cout<<"*	退出，请输入除以上操作指令的任意数"<<endl;
    cout<<"************************************************"<<endl;
}

Status InitList(SqList & L){
    L.elem=new Student[MAXSIZE];
    if(!L.elem){
        cout<<"初始化失败"<<endl;
        return ERROR;
    }
    L.length=0;
    return OK;
}

void DestroyList(SqList & L){
    if(L.elem){
		delete[] L.elem;
    }
    L.length=0;
    L.elem=NULL;

}

void ClearList(SqList & L){
    L.length=0;
}
bool IsEmpty(SqList & L){
    if(L.length==0){
        return true;
    }
    return false;
}
int GetLen(SqList & L){
    return L.length;
}

Status GetElem(SqList&L,int i,Student & stu){
    if(i<1||i>L.length){
    	cout<<"查询位置有误"<<endl;
    	return ERROR;
	}
	else{
		stu=L.elem[i-1];
		return OK;
	}      
}

Status PreElem(SqList&L,int i,Student & stu){
    if(i==1){
        cout<<"线性表第一个位置没有前驱"<<endl;
        return ERROR;
    }
    else if(i<1||i>L.length){
    	cout<<"查询位置有误"<<endl;
    	return ERROR;
	}
	else{
		stu=L.elem[i-2];
		return OK;
	}
}

Status NextElem(SqList&L,int i,Student & stu){ 
    if(i==L.length){
        cout<<"线性表最后一个位置没有后继"<<endl;
        return ERROR;
    }
    else if(i<1||i>L.length){
    	cout<<"查询位置有误"<<endl;
    	return ERROR;
	}
	else{
		stu=L.elem[i];
		return OK;
	}    
}

Status ListInsert(SqList&L,int i,Student stu){
    if((i<1) || (i>L.length+1)){
        cout<<"插入位置有误"<<endl;
        return ERROR;
    }
    else if(L.length==MAXSIZE){
        cout<<"存储空间已满"<<endl;
        return ERROR;
    }
    else{
        for(int j=L.length-1;j>=i-1;j--){
            L.elem[j+1]=L.elem[j];
        }
        L.elem[i-1]=stu;
        L.length++;
        return OK;
    }
}

Status ListDelete(SqList&L,int i){
    if((i<1)||(i>L.length)){
        cout<<"删除位置有误"<<endl;
        return ERROR;
    }
    else{
        for(int j=i;j<=L.length-1;j++){
            L.elem[j-1]=L.elem[j];
        }
        L.length--;
        return OK;
    }
}

void ShowList(SqList&L){
	cout<<endl;
	cout<<"姓名\t性别\t年龄"<<endl;
    for(int i=0;i<L.length;i++){
        cout<<L.elem[i].name<<"\t"<<L.elem[i].gender<<"\t"<<L.elem[i].age<<endl;
    }
}
int main()
{
    while(true){
        menu();
        cout<<"请输入操作代码:";
        int n;
        cin>>n;
        SqList L;
        switch(n){
        case 1:
        	{
        		InitList(L);
            	break;
			}
            
        case 2:
        	{
        		DestroyList(L);
            	break;
			}
        case 3:
        	{
        		ClearList(L);
            	break;
			}
        case 4:
        	{
        		if(IsEmpty(L)){
                cout<<"线性表为空"<<endl;
           		}
            	else{
                	cout<<"线性表不为空"<<endl;
            	}
            	break;	
			}
        case 5:
        	{
	        	int len=GetLen(L);
	            cout<<"线性表长度为"<<len<<endl;
	            break;
			}
        case 6:
        	{
	        	int index;
	            cout<<"请输入你想查看线性表的位置:";
	            cin>>index;
	            Student stu;
	            if(GetElem(L,index,stu)){
	            	cout<<stu.name<<"\t"<<stu.gender<<"\t"<<stu.age<<endl;	
				}
	            
	            break;
	        		
			}
        case 7:
        	{
	        	int index;
	            cout<<"请输入你想查看线性表哪个位置的前驱:";
	            cin>>index;
	            Student stu;
	            if(PreElem(L,index,stu)){
	            	cout<<stu.name<<"\t"<<stu.gender<<"\t"<<stu.age<<endl;
				}
	            break;
        		
			}
        case 8:
        	{
	        	int index;
	            cout<<"请输入你想查看线性表哪个位置的后继:";
	            cin>>index;
	            Student stu;
	            if(NextElem(L,index,stu)){
	           		cout<<stu.name<<"\t"<<stu.gender<<"\t"<<stu.age<<endl;
	           	}
	            break;
			}
        case 9:
        	{
	        	int index;
	            cout<<"请输入你想在线性表哪个位置插入元素:";
	            cin>>index;
	            string name;
	            string gender;
	            int age;
	            cout<<"请输入学生姓名:";
	            cin>>name;
	            cout<<"请输入学生性别(男或女):";
	            cin>>gender;
	            cout<<"请输入学生年龄:";
	            cin>>age;
	            Student stu;
	            stu.name=name;
	            stu.gender=gender;
	            stu.age=age;
	            int sta=ListInsert(L,index,stu);
	            break;
			}
            
        case 10:
        	{
	        	int index;
	            cout<<"请输入你想删除线性表哪个位置的元素:";
	            cin>>index;
	            int sta=ListDelete(L,index);
	            break;
			}
        case 11:
        	{
        		ShowList(L);
            	break;	
			}

        default:
            return 0;
        }
        cout<<endl;
    }
    return 0;
}
  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
  144
  145
  146
  147
  148
  149
  150
  151
  152
  153
  154
  155
  156
  157
  158
  159
  160
  161
  162
  163
  164
  165
  166
  167
  168
  169
  170
  171
  172
  173
  174
  175
  176
  177
  178
  179
  180
  181
  182
  183
  184
  185
  186
  187
  188
  189
  190
  191
  192
  193
  194
  195
  196
  197
  198
  199
  200
  201
  202
  203
  204
  205
  206
  207
  208
  209
  210
  211
  212
  213
  214
  215
  216
  217
  218
  219
  220
  221
  222
  223
  224
  225
  226
  227
  228
  229
  230
  231
  232
  233
  234
  235
  236
  237
  238
  239
  240
  241
  242
  243
  244
  245
  246
  247
  248
  249
  250
  251
  252
  253
  254
  255
  256
  257
  258
  259
  260
  261
  262
  263
  264
  265
  266
  267
  268
  269
  270
  271
  272
  273
  274
  275
  276
  277
  278
  279
  280
  281
  282
  283
  284
  285
  286
  287
  288
  289
  290
  291
  292
  293
  294
  295
  296
  297
  298
  299

链式存储结构

#include <bits/stdc++.h>
#include <iostream>
#include <string>
#define MAXSIZE 100
#define OK 1;
#define ERROR 0;
using namespace std;
typedef int Status;

typedef struct{
    string name;
    string gender;
    int age;
}Student;

typedef struct LNode{
	Student stu;
	struct LNode * next;
}LNode,*LinkList;
void menu(){
	cout<<"************************************************"<<endl;
    cout<<"*	1----初始化一个线性表"<<endl;
    cout<<"*	2----销毁线性表"<<endl;
    cout<<"*	3----清空线性表"<<endl;
    cout<<"*	4----判断线性表是否为空"<<endl;
    cout<<"*	5----求线性表长度"<<endl;
    cout<<"*	6----获取线性表指定位置元素"<<endl;
    cout<<"*	7----求前驱"<<endl;
    cout<<"*	8----求后继"<<endl;
    cout<<"*	9----在线性表指定位置插入元素"<<endl;
    cout<<"*	10----删除线性表指定位置元素"<<endl;
    cout<<"*	11----显示线性表"<<endl;
    cout<<"*	退出，请输入除以上操作指令的任意数"<<endl;
    cout<<"************************************************"<<endl;
}
void InitList(LinkList & L){
	L=new LNode;
	L->next=NULL;
}

Status GetElem(LinkList L,int i,Student & stu){
	if(!L->next){
		cout<<"请先初始化一个线性表"<<endl;
		return ERROR;
	}
	LinkList p=L->next;
	int j=1;
	while(p&&j<i){
		p=p->next;
		j++;
	}
	if(!p||j>i){
		cout<<"i输入不合法"<<endl;
		return ERROR;
	}
	stu=p->stu;
	return OK;
}

void DestroyList(LinkList L){    //连带头结点也一起删除了
	LinkList s=L;
	while(s){
		LinkList p=s;
		s=s->next;
		delete p;
	}
}

void ClearList(LinkList L){
	LinkList s=L->next;
    while(s){
		LinkList p=s;
		s=s->next;
		delete p;
	}
}

bool IsEmpty(LinkList L){
    if(L->next){
		return false;
	}
    return true;
}

int GetLen(LinkList L){
    int j=0;
	LinkList s=L;
	while(s){
		s=s->next;
		j++;
	}
	return j;
}

Status PreElem(LinkList&L,int i,Student & stu){
    if(i==1){
        cout<<"线性表第一个位置没有前驱"<<endl;
        return ERROR;
    }
    else if(i<1||i>GetLen(L)){
    	cout<<"查询位置有误"<<endl;
    	return ERROR;
	}
	else{
		GetElem(L,i-1,stu);
		return OK;
	}
}

Status NextElem(LinkList&L,int i,Student & stu){ 
    if(i==GetLen(L)){
        cout<<"线性表最后一个位置没有后继"<<endl;
        return ERROR;
    }
    else if(i<1||i>GetLen(L)){
    	cout<<"查询位置有误"<<endl;
    	return ERROR;
	}
	else{
		GetElem(L,i+1,stu);
		return OK;
	}   
}
LNode * LocateElem(LinkList L,Student stu){
	LinkList p=L->next;
	while(p&&(p->stu.name!=stu.name ||  p->stu.gender!=stu.gender || p->stu.age!=stu.age)){
		p=p->next;
	}
	return p;
}

Status ListInsert(LinkList & L,int i,Student stu){
	LinkList p=L;
	int j=0;
	while(p&&(j<i-1)){
		p=p->next;
		j++;
	}
	if(!p||j>i-1){
		cout<<"i输入不合法"<<endl;
		return ERROR;
	}
	LinkList s=new LNode;
	s->stu=stu;
	s->next=p->next;
	p->next=s;
	return OK;
}

Status ListDelete(LinkList &L,int i){
	LinkList p=L;
	int j=0;
	while((p->next)&&(j<i-1)){
		p=p->next;
		j++;
	}
	if(!(p->next)||(j>i-1)){
		cout<<"i输入不合法"<<endl;
		return ERROR;
	}
	LinkList q=p->next;
	p->next=q->next;
	delete q;
	return OK;
}

void ShowList(LinkList&L){
	cout<<endl;
	cout<<"姓名\t性别\t年龄"<<endl;
	LinkList p=L->next;
	while(p){
		cout<<p->stu.name<<"\t"<<p->stu.gender<<"\t"<<p->stu.age<<endl;
		p=p->next;
	}
}
int main()
{
	int flag=0;
    while(true){
        menu();
        cout<<"请输入操作代码:";
        int n;
        cin>>n;
        LinkList L;
        switch(n){
        case 1:
        	{
        		InitList(L);
        		flag=1;
            	break;
			}
            
        case 2:
        	{
        		if(!flag){
        			cout<<"请先初始化线性表"<<endl; 
        			break;
        		}
        		DestroyList(L);
        		flag=0;
            	break;
			}
        case 3:
        	{
        		if(!flag){
        			cout<<"请先初始化线性表"<<endl; 
        			break;
        		}
        		ClearList(L);
            	break;
			}
        case 4:
        	{
        		if(!flag){
        			cout<<"请先初始化线性表"<<endl; 
        			break;
        		}
        		if(IsEmpty(L)){
                cout<<"线性表为空"<<endl;
           		}
            	else{
                	cout<<"线性表不为空"<<endl;
            	}
            	break;	
			}
        case 5:
        	{
        		if(!flag){
        			cout<<"请先初始化线性表"<<endl; 
        			break;
        		}
	        	int len=GetLen(L);
	            cout<<"线性表长度为"<<len<<endl;
	            break;
			}
        case 6:
        	{
        		if(!flag){
        			cout<<"请先初始化线性表"<<endl; 
        			break;
        		}
	        	int index;
	            cout<<"请输入你想查看线性表的位置:";
	            cin>>index;
	            Student stu;
	            if(GetElem(L,index,stu)){
	            	cout<<stu.name<<"\t"<<stu.gender<<"\t"<<stu.age<<endl;	
				}
	            
	            break;
	        		
			}
        case 7:
        	{
        		if(!flag){
        			cout<<"请先初始化线性表"<<endl; 
        			break;
        		}
	        	int index;
	            cout<<"请输入你想查看线性表哪个位置的前驱:";
	            cin>>index;
	            Student stu;
	            if(PreElem(L,index,stu)){
	            	cout<<stu.name<<"\t"<<stu.gender<<"\t"<<stu.age<<endl;
				}
	            break;
        		
			}
        case 8:
        	{
        		if(!flag){
        			cout<<"请先初始化线性表"<<endl; 
        			break;
        		}
	        	int index;
	            cout<<"请输入你想查看线性表哪个位置的后继:";
	            cin>>index;
	            Student stu;
	            if(NextElem(L,index,stu)){
	           		cout<<stu.name<<"\t"<<stu.gender<<"\t"<<stu.age<<endl;
	           	}
	            break;
			}
        case 9:
        	{
        		if(!flag){
        			cout<<"请先初始化线性表"<<endl; 
        			break;
        		}
	        	int index;
	            cout<<"请输入你想在线性表哪个位置插入元素:";
	            cin>>index;
	            string name;
	            string gender;
	            int age;
	            cout<<"请输入学生姓名:";
	            cin>>name;
	            cout<<"请输入学生性别(男或女):";
	            cin>>gender;
	            cout<<"请输入学生年龄:";
	            cin>>age;
	            Student stu;
	            stu.name=name;
	            stu.gender=gender;
	            stu.age=age;
	            ListInsert(L,index,stu);
	            break;
			}
            
        case 10:
        	{
        		if(!flag){
        			cout<<"请先初始化线性表"<<endl; 
        			break;
        		}
	        	int index;
	            cout<<"请输入你想删除线性表哪个位置的元素:";
	            cin>>index;
	            int sta=ListDelete(L,index);
	            break;
			}
        case 11:
        	{
        		if(!flag){
        			cout<<"请先初始化线性表"<<endl; 
        			break;
        		}
        		ShowList(L);
            	break;	
			}

        default:
            return 0;
        }
		cout<<endl;
    }
    return 0;
}

  
 
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20
  21
  22
  23
  24
  25
  26
  27
  28
  29
  30
  31
  32
  33
  34
  35
  36
  37
  38
  39
  40
  41
  42
  43
  44
  45
  46
  47
  48
  49
  50
  51
  52
  53
  54
  55
  56
  57
  58
  59
  60
  61
  62
  63
  64
  65
  66
  67
  68
  69
  70
  71
  72
  73
  74
  75
  76
  77
  78
  79
  80
  81
  82
  83
  84
  85
  86
  87
  88
  89
  90
  91
  92
  93
  94
  95
  96
  97
  98
  99
  100
  101
  102
  103
  104
  105
  106
  107
  108
  109
  110
  111
  112
  113
  114
  115
  116
  117
  118
  119
  120
  121
  122
  123
  124
  125
  126
  127
  128
  129
  130
  131
  132
  133
  134
  135
  136
  137
  138
  139
  140
  141
  142
  143
  144
  145
  146
  147
  148
  149
  150
  151
  152
  153
  154
  155
  156
  157
  158
  159
  160
  161
  162
  163
  164
  165
  166
  167
  168
  169
  170
  171
  172
  173
  174
  175
  176
  177
  178
  179
  180
  181
  182
  183
  184
  185
  186
  187
  188
  189
  190
  191
  192
  193
  194
  195
  196
  197
  198
  199
  200
  201
  202
  203
  204
  205
  206
  207
  208
  209
  210
  211
  212
  213
  214
  215
  216
  217
  218
  219
  220
  221
  222
  223
  224
  225
  226
  227
  228
  229
  230
  231
  232
  233
  234
  235
  236
  237
  238
  239
  240
  241
  242
  243
  244
  245
  246
  247
  248
  249
  250
  251
  252
  253
  254
  255
  256
  257
  258
  259
  260
  261
  262
  263
  264
  265
  266
  267
  268
  269
  270
  271
  272
  273
  274
  275
  276
  277
  278
  279
  280
  281
  282
  283
  284
  285
  286
  287
  288
  289
  290
  291
  292
  293
  294
  295
  296
  297
  298
  299
  300
  301
  302
  303
  304
  305
  306
  307
  308
  309
  310
  311
  312
  313
  314
  315
  316
  317
  318
  319
  320
  321
  322
  323
  324
  325
  326
  327
  328
  329
  330
  331
  332
  333
  334
  335
  336
  337
  338
  339
  340
  341
  342
  343
  344
  345
  346
  347
  348
  349
  350
  351
  352
  353
  354
  355
  356
  357
  358
  359
  360
  361
  362
  363
  364
  365
  366

如果有错误，还望指正😉

文章来源: blog.csdn.net，作者：开心星人，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_55675216/article/details/123647408

点赞
收藏
关注作者

作者其他文章

抱歉，系统识别当前为高风险访问，暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称，即可参与社区互动！

*长度不超过10个汉字或20个英文字符，设置后3个月内不可修改。

确认取消

开发者空间

了解空间

工作台

开发工具

实战案例

空间活动

空间论坛

开发平台

软件开发生产线 CodeArts

AI平台ModelArts

数据治理中心 DataArts Studio

数字内容生产线 MetaStudio

精选服务

云数据库 GaussDB

云数据库 RDS for MySQL

MapReduce服务 MRS

数据仓库服务 DWS

分布式缓存服务Redis版

分布式消息服务 DMS

华为云实时音视频 SparkRTC

媒体处理 MPC

主机迁移服务 SMS

对象存储迁移服务 OMS

云消息服务 KooMessage

云手机服务 KooPhone

企业搜索服务 KooSearch

云地图服务 KooMap

更多开放能力

开发工具

API生态

CodeArts API

API Explorer

Terraform Explorer

KooCLI

API 中心

SDK 中心

开发服务

Codelabs

DevStar

低代码平台Astro

CodeArts IDE

Huawei Cloud Toolkit

Classroom

开发资源

开源镜像站

开源资源

开发语言

开发实践

入门精选

分发资源

企业应用中心

企业通用专区

教育专区

华为应用专区

政务云专区

硬件云服务商城

医疗健康专区

跳蚤市场

华为云开发者日

直播专区

开发者精品活动

DTSE Tech Talk

加入HCDE

加入HCDG

加入HCSD

加入HCWD

鲁班会

沃土云创计划·企业

沃土云创计划·高校

沃土云创计划·个人

沃土云创计划·开源共创

博客

论坛

专题

开发者榜单

学习路径

在线课程

动手实验

考试认证

培训服务