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

举报
开心星人 发表于 2022/06/29 23:52:20 2022/06/29
【摘要】 文章目录 顺序存储结构链式存储结构 顺序存储结构 //#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

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

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

全部回复

上滑加载中

设置昵称

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

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

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