数据结构--线性表（顺序表）

// // main.c // SLDemo // // Created by 娄坤 on 2018/4/9. // Copyright © 2018年 娄坤. All rights reserved. // /* 实验要求： 1：建立一个顺序表 完成 2:顺序表的长度并输出顺序表 完成 3:插入元素的位置和元素 4:删除值为x的元素 5:顺序表倒置 6:将顺序表按升序排序 7:将两个有序表A和B合并为一个有序表C */ #include <stdio.h> #include <string.h> #include <stdlib.h> typedef struct //定义一个结构体存储学生信息 { char name[20]; char sex[10]; int age; char id[20]; char addr[30]; } ElemStu; typedef struct //定义一个结构体存储学生结构体 ，即使用链表模式 { ElemStu *elem; //定义一个线性表 int length;//定义线性表的长度 } Seqlist; //创建线性表，向线性表中添加数据 void creat_Seqlist(Seqlist *thelist,int n)//采用结构体指针作为形参接收函数传过来的地址 { int i; thelist->elem = (ElemStu*)malloc(n*sizeof(ElemStu));//动态为线性表分配内存空间 for (i = 0; i < n; i++) { printf("请输入第%d个学生姓名：\n",i+1); gets(thelist->elem[i].name); printf("请输入第%d个学生性别：\n",i+1); gets(thelist->elem[i].sex); printf("请输入第%d个学生年龄：\n",i+1); scanf("%d",&(thelist->elem[i].age)); getchar();//将回车键吃掉 printf("请输入第%d个学生学号：\n",i+1); gets(thelist->elem[i].id); printf("请输入第%d个学生住址：\n",i+1); gets(thelist->elem[i].addr); } thelist->length = n;//为线性表的长度赋值 } //打印线性表中的内容 void print_Seqlist(Seqlist *thelist) { int i; printf("顺序表的长度为:%d\n",thelist->length);//打印输出顺序表的长度 printf("姓名\t性别\t年龄\t学号\t住址\n"); for(i = 0; i < thelist->length; i++)//打印顺序表中的元素 { printf("%s\t%s\t%d\t%s\t%s\n",thelist->elem[i].name,thelist->elem[i].sex,thelist->elem[i].age,thelist->elem[i].id,thelist->elem[i].addr); } } //插入元素 void InsertElem(Seqlist *thelist){ int i,h; int k,p; char name2[20],sex2[10],id2[10],addr2[20]; int age2; printf("请选择要插入元素的位置:\n"); scanf("%d",&h); getchar(); printf("请输入要插入的学生信息：\n"); printf("请输入学生姓名：\n"); gets(name2); printf("请输入学生性别：\n"); gets(sex2); printf("请输入学生年龄：\n"); scanf("%d",&age2); getchar();//将回车键吃掉 printf("请输入学生学号：\n"); gets(id2); printf("请输入学生住址：\n"); gets(addr2); i = thelist->length-h+1;k=thelist->length;p=thelist->length-1; while(i--){ thelist->elem[k] = thelist->elem[p]; k--;p--; } strcpy(thelist->elem[h-1].name, name2);//将姓名插入进去 strcpy(thelist->elem[h-1].sex, sex2);//将性别插入进去 thelist->elem[h-1].age = age2;//将年龄插入进去 strcpy(thelist->elem[h-1].id, id2);//将学号插入进去 strcpy(thelist->elem[h-1].addr, addr2);//将住址插入进去 thelist->length++;//顺序表长度加一 printf("插入后的顺序表为：\n"); printf("姓名\t性别\t年龄\t学号\t住址\n"); for(i = 0; i < thelist->length; i++)//打印顺序表中的元素 { printf("%s\t%s\t%d\t%s\t%s\n",thelist->elem[i].name,thelist->elem[i].sex,thelist->elem[i].age,thelist->elem[i].id,thelist->elem[i].addr); } } //根据姓名和学号查找相关学生的信息 int find_data(Seqlist *thelist){ int i = 0; char name[20];//定义一个数组用来存放要查找的学生的姓名 char id[5];//定义一个数组用来存放要查找的学生的学号 printf("请输入姓名：\n"); scanf("%s",name); printf("请输入学号：\n"); scanf("%s",id); while (i <=thelist->length) { if((strcmp(name,thelist->elem[i].name)==0)&&(strcmp(id,thelist->elem[i].id)==0)){ printf("姓名\t性别\t年龄\t学号\t住址\n"); printf("%s\t%s\t%d\t%s\t%s\n",thelist->elem[i].name,thelist->elem[i].sex,thelist->elem[i].age,thelist->elem[i].id,thelist->elem[i].addr); return i; } i++; } printf("没找到相关学生信息"); return -1; } //删除顺序表中的某个学生的信息 int delData(Seqlist *thelist){ int item = find_data(thelist); if(item != -1){ int i = 0; i = item; for (i = 0; i < thelist->length-1; i++) { thelist->elem[i] = thelist->elem[i+1]; } thelist->length --; } return 0; } //顺序表的倒置 void Invert_Array(Seqlist *thelist){ int i; ElemStu myStu;//创建一个学生的结构体用来做为转置的中间参数 if (thelist->length == 1){ return ; } for(i = 0;i < thelist->length/2;i++){ myStu = thelist->elem[i]; thelist->elem[i] = thelist->elem[thelist->length-i-1]; thelist->elem[thelist->length-i-1] = myStu; } printf("倒置后的顺序表为：\n"); printf("姓名\t性别\t年龄\t学号\t住址\n"); for(i = 0; i < thelist->length; i++)//打印顺序表中的元素 { printf("%s\t%s\t%d\t%s\t%s\n",thelist->elem[i].name,thelist->elem[i].sex,thelist->elem[i].age,thelist->elem[i].id,thelist->elem[i].addr); } } //将顺序表按学号升序排序 void Bubble_Sort_up(Seqlist *thelist){ int i,j,flag=0; ElemStu stu; for(i = 1;i<thelist->length;i++){ flag=1; for(j=0;j<thelist->length-i;j++){ flag=0; if(strcmp(thelist->elem[j].id , thelist->elem[j+1].id) > 0){ stu = thelist->elem[j]; thelist->elem[j] = thelist->elem[j+1]; thelist->elem[j+1] = stu; } } if (flag) {//让排序提前结束 break; } } printf("排序后的结果为：\n"); printf("姓名\t性别\t年龄\t学号\t住址\n"); for(i = 0;i < thelist->length;i++){ printf("%s\t%s\t%d\t%s\t%s\n",thelist->elem[i].name,thelist->elem[i].sex,thelist->elem[i].age,thelist->elem[i].id,thelist->elem[i].addr); } } //将两个有序表A和B合并为一个有序表C(单纯的对数组进行合并，不涉及到结构体) void CombaneArray(){ int n,m,*arrayA,*arrayB,*arrayC;//定义三个指针变量存放数组元素 int i = 0,j=0,k = 0; printf("请输入数组A所含元素的个数:\n"); scanf("%d",&n); arrayA = (int *)malloc(n*sizeof(int));//动态为数组A分配内存大小 printf("随机输入%d个有序个数（从大到小)：\n",n); for (i = 0; i < n; i++) { scanf("%d",&arrayA[i]); } printf("请输入数组B所含元素的个数:\n"); scanf("%d",&m); arrayB = (int*)malloc(m*sizeof(int));//动态为数组B分配内存大小 printf("随机输入%d个有序个数（从大到小）:\n",n); for (j = 0; j < m; j++) { scanf("%d",&arrayB[j]); } j = 0;i = 0; arrayC = (int *)malloc((m+n)*sizeof(int));//动态为合并后的数组C分配内存 while (i <n&&j<m) { if(arrayA[i]>arrayB[j]){ arrayC[k++] = arrayB[j++]; }else{ arrayC[k++] = arrayA[i++]; } } if(i < n){ while (i<n) { arrayC[k++] = arrayA[i++]; } }else{ while (j<m) { arrayC[k++] = arrayB[j++]; } } for (int i = 0;i < m+n;i++){ printf("%d ",arrayC[i]); } printf("\n"); } //操作菜单 void menu(){ printf("-------顺序表的操作---------\n"); printf(" 1.建立一个顺序表 \n"); printf(" 2.打印顺序表的长度并输出顺序表 \n"); printf(" 3.插入元素的位置和元素 \n"); printf(" 4.按照姓名和学号删除顺序表中的(某个学生信息)元素\n"); printf(" 5.顺序表倒置 \n"); printf(" 6.将顺序表按学号升序排序:\n"); printf(" 7.将两个有序表A和B合并为一个有序表C:\n"); printf(" 8.查看顺序表中的某个元素:\n"); printf(" 0.谢谢使用 \n"); printf("-------顺序表的操作---------\n"); } //主函数 int main() { int n; Seqlist mySeq_class;//初始化结构体 mySeq_class.length = 0;//为结构体长度赋初值为0 int m; while(1){ menu(); printf("请输入操作序号:\n"); scanf("%d",&m); switch (m) { case 1://创建线性表 printf("请输入添加的学生个数\n"); scanf("%d",&n); getchar();//将输入的回车吃掉 creat_Seqlist(&mySeq_class,n);// 调用creat_Sqlist 将mySl_class的地址作为实参传递 break; case 2://打印顺序表 print_Seqlist(&mySeq_class);// 将mySql_class的地址作为实参传递 break; case 3://顺序表的插入操作 InsertElem(&mySeq_class); break; case 4://顺序表的删除操作，删除结构体数组中某位学生的信息 delData(&mySeq_class); break; case 5://顺序表倒置 Invert_Array(&mySeq_class); break; case 6://将顺序表按学号顺序排序 Bubble_Sort_up(&mySeq_class); break; case 7://将两个有序数组A和B合并为一个有序表C CombaneArray(); break; case 8://查找顺序表中的某个学生的信息 find_data(&mySeq_class); break; default: return 0; break; } } return 0; }

顺序表算是线性表中最简单，最基础的数据结构，可能在进行顺序表的操作中，唯一相对来说较为难理解的是有关于&符号的作用，以及指针的使用，指针贯穿整个数据结构的内容，所以必需得熟知。