顺序表:
概念:用一组地址连续的存储单元依次存储线性表的数据元素,这种存储结构的线性表称为顺序表。
特点:逻辑上相邻的数据元素,物理次序也是相邻的。
实现:
用结构体定义一本图书:
typedef struct {
int id;
char name[20];
double price;
}Book;//创建一本书的元素
创建线性表:
typedef struct _node {
Book* b;
int length;
}Seqlist;//线性表的创建
初始化顺序表:
void inlitist(Seqlist* L) {
L->b = (Book*)malloc(sizeof(Book) * 100);//给图书信息结构体分配一块内存空间
L->length = 0;
}//初始化链表
顺序表的输入:
void creatlist(Seqlist* L, int n) {
int i;
for (i = 0; i < n; i++) {
printf("请输入书号\n");
scanf("%d", &L->b[i].id);
printf("请输入书名\n");
scanf("%s", L->b[i].name);
printf("请输入价格\n");
scanf("%lf", &L->b[i].price);
L->length++; //每输入一本图书信息,就增加表长
}
system("pause");
system("cls");
}//创建链表
顺序表的输出:
void printflist(Seqlist* L) {
int i;
for (i = 0; i < L->length; i++) {
printf("%d %s %.2lf\n", L->b[i].id, L->b[i].name, L->b[i].price);
}//历遍顺序表
}//输出链表所有的数据
插入顺序表:
void inselem(Seqlist* L, int i) {
int j;
if (L->length >= 100) {
printf("表已满,无法插入!");//此处定义的表长最大为100
}
if (i<1 || i>L->length) {
printf("插入位置错误!\n");
return error;
}
for (j = L->length - 1; j >= i - 1; j--) {//将最后的元素依次后移,到i-1这个条件停止(即插末尾的下标减掉插入位置的数值是要移动的次数)
L->b[j + 1] = L->b[j];//右移(L->length-1向右移一位即是+1)
printf("请输入插入的书号\n");
scanf("%d", &L->b[i - 1].id);
printf("请输入插入的书名\n");
scanf("%s", L->b[i - 1].name);
printf("请输入插入的价格\n");
scanf("%lf", &L->b[i - 1].price);
L->length++;
return ok;
}
system("pause");//暂停
system("cls");//清屏
}//插入数据
插入图解:
注意:插入前要检查表是否已经满了以及位置是否小于表的第一个位置和表的最大长度。我们想要插入元素,就先要明白顺序表是按照顺序存储的,想要插入,就先把插入位置后面的元素全部后移一位,那从哪里开始移动呢,因为顺序结构,肯定不能从插入位置后面的元素移动,否则就就会占到他的下一个元素的位置从而丢失元素,因此先从最后一个元素开始移动。最后一个元素的下标是L->length-1,右移一个位置是+1,经过j--后将指针指向最后一个元素的前一个元素,右移一个单位,依次类推,那么,达到什么条件才能让这个循环停止,是最后一个元素的下标减去要插入位置的下标的得出的结果就是循环的次数,因此当j--等于插入位置的下标时,循环停止,插入位置后面的元素全部后移,插入的位置就空出来,就可以插入元素了,插入后防止溢出需要将表长+1
删除:
void deletelist(Seqlist* L, int i) {
int j;
Book* x = L->b;
if (L->length == NULL) {
printf("表空,无法删除\n");
return error;
}
if (i<1 || i>L->length) {
printf("不存在第i个元素\n");
return error;
}
*x = L->b[i - 1];
for (j = i; j < L->length; j++) {
L->b[j - 1] = L->b[j];//左移
L->length--;
return ok;
}
system("pause");//暂停
system("cls");//清屏
}//删除
图解删除:
删除元素,先要判断表是否为空和删除的元素是否小于表的第一个元素或者大于表的最大空间,否则无元素删除。先要找到元素所处的位置(设为i),先定义一个Book类型的指针变量,将顺序表的数据域赋值给这个指针, 就可以通过这个指针对元素进行操作了,将i中的元素放入指针变量*x中,在i处(下标为i-1)就空出位置,因此要左移后面剩下的元素(可以不移动吗,我们要注意这个是顺序表,是不能空缺的,这样子才是一个完整的顺序表)。循环终止条件:依旧是最后一个元素的位置减去要插入的位置,当j=i,从i的位置(已经空出来的位置)开始一步步将元素左移,j++是移动一个下一个,直到j达到表中最后一个元素
查找:
int locate1(Seqlist* L, int i) {
int j = 0;
while (j < L->length && L->b[j].id != i) {
j++;
}
if (j >= L->length) {
return error;
}
else {
return j + 1;
}
}//按照书号查找
int locate2(Seqlist* L, char name1[20]) {
int j = 0;
while (j < L->length && L->b[j].name != name1) {
j++;
}
if (j >= L->length) {
return error;
}
else {
return j + 1;
}//按照书名查找
}int locate3(Seqlist* L, double piece1) {
int j = 0;
while (j < L->length && L->b[j].price != piece1) {
j++;
}
if (j >= L->length) {
return error;
}
else {
return j + 1;
}
}//按照价格查找
int getlist(Seqlist* L, int i) {
if (i<1 || i>L->length) {
return error;
}
else {
printf("要查找的位置的数据为:\n");
printf("%d %s %.2lf\n", L->b[i - 1].id, L->b[i - 1].name, L->b[i - 1].price);
}
}//按照位置查找元素
以上这三个(书号、书名、价格)查找,理论上是差不多的,通过j=0(数组下标从0开始)来定位要查找元素的位置,然后输出来,最后一个查找,通过位置查找,则下标为i-1就是所查找的元素
最后源代码:
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#include<stdlib.h>
#pragma warning (disable:4996)
#define error 0 //错误
#define ok 1 //正确
typedef struct {
int id;
char name[20];
double price;
}Book;//创建一本书的元素
typedef struct _node {
Book* b;
int length;
}Seqlist;//线性表的创建
void welcome() {
printf("1.创建并输出链表\n");
printf("2.插入线性表\n");
printf("3.删除线性表\n");
printf("4.按书号查找\n");
printf("5.按书名查找\n");
printf("6.按价格查找\n");
printf("7.按照位置查找元素\n");
printf("0.退出\n");
}//欢迎
void inlitist(Seqlist* L) {
L->b = (Book*)malloc(sizeof(Book) * 100);
L->length = 0;
}//初始化链表
void creatlist(Seqlist* L, int n) {
int i;
for (i = 0; i < n; i++) {
printf("请输入书号\n");
scanf("%d", &L->b[i].id);
printf("请输入书名\n");
scanf("%s", L->b[i].name);
printf("请输入价格\n");
scanf("%lf", &L->b[i].price);
L->length++; //每输入一本图书信息,就增加表长
}
system("pause");
system("cls");
}//创建链表
void printflist(Seqlist* L) {
int i;
for (i = 0; i < L->length; i++) {
printf("%d %s %.2lf\n", L->b[i].id, L->b[i].name, L->b[i].price);
}//历遍顺序表
}//输出链表所有的数据
void inselem(Seqlist* L, int i) {
int j;
if (L->length >= 100) {
printf("表已满,无法插入!");//此处定义的表长最大为100
}
if (i<1 || i>L->length) {
printf("插入位置错误!\n");
return error;
}
for (j = L->length - 1; j >= i - 1; j--) {
L->b[j + 1] = L->b[j];
printf("请输入插入的书号\n");
scanf("%d", &L->b[i - 1].id);
printf("请输入插入的书名\n");
scanf("%s", L->b[i - 1].name);
printf("请输入插入的价格\n");
scanf("%lf", &L->b[i - 1].price);
L->length++;
return ok;
}
system("pause");//暂停
system("cls");//清屏
}//插入数据
void deletelist(Seqlist* L, int i) {
int j;
Book* x = L->b;
if (L->length == NULL) {
printf("表空,无法删除\n");
return error;
}
if (i<1 || i>L->length) {
printf("不存在第i个元素\n");
return error;
}
*x = L->b[i - 1];
for (j = i; j < L->length; j++) {
L->b[j - 1] = L->b[j];
L->length--;
return ok;
}
system("pause");//暂停
system("cls");//清屏
}//删除
int locate1(Seqlist* L, int i) {
int j = 0;
while (j < L->length && L->b[j].id != i) {
j++;
}
if (j >= L->length) {
return error;
}
else {
return j + 1;
}
}//按照书号查找
int locate2(Seqlist* L, char name1[20]) {
int j = 0;
while (j < L->length && L->b[j].name != name1) {
j++;
}
if (j >= L->length) {
return error;
}
else {
return j + 1;
}//按照书名查找
}int locate3(Seqlist* L, double piece1) {
int j = 0;
while (j < L->length && L->b[j].price != piece1) {
j++;
}
if (j >= L->length) {
return error;
}
else {
return j + 1;
}
}//按照价格查找
int getlist(Seqlist* L, int i) {
if (i<1 || i>L->length) {
return error;
}
else {
printf("要查找的位置的数据为:\n");
printf("%d %s %.2lf\n", L->b[i - 1].id, L->b[i - 1].name, L->b[i - 1].price);
}
}//按照位置查找元素
int main() {
Seqlist L;
int n, i, loc;
char ch1, ch2, a;
char name1[20];
double piece1;
ch1 = 'y';
while (ch1 == 'y') {
welcome();
ch2 = getch();
switch (ch2) {
case'1':
inlitist(&L);
printf("请输入要建立线性表的个数\n");
scanf("%d", &n);
creatlist(&L, n);
printf("输入的数据为:\n");
printflist(&L);
break;
case'2':
printf("请输入要插入的位置\n");
scanf("%d", &i);
inselem(&L, i);
printf("插入后的线性表为:\n");
printflist(&L);
break;
case'3':
printf("请输入要删除的位置\n");
scanf("%d", &i);
deletelist(&L, i);
printf("删除后的链表为:\n");
printflist(&L);
break;
case'4':
printf("请输入要查找的书号\n");
scanf("%d", &i);
loc = locate1(&L, i);
if (loc) {
printf("查找书号%d的位置为:%d\n", i, loc);
}
else {
printf("表中无该元素\n");
}
break;
case'5':
printf("请输入要查找的书名\n");
scanf("%s", name1);
loc = locate2(&L, name1);
if (loc) {
printf("查找书名%s的位置为:%d\n", name1, loc);
}
else {
printf("该表中没有该书名\n");
}
break;
case'6':
printf("请输入要查找的价格\n");
scanf("%lf", &piece1);
loc = locate3(&L, piece1);
if (loc) {
printf("查找价格%.2lf的位置为:%d\n", piece1, loc);
}
else {
printf("该表中没有该价格\n");
}
break;
case'7':
printf("请输入要查找位置的数据\n");
scanf("%d", &i);
getlist(&L, i);
break;
case'0':
printf("欢迎下次使用!!!\n");
exit(error);
break;
}
}
}
最后效果:
创建并输出,在插入:
删除
按照书号查找:
按价格查找:
按位置查找:
最后本人是新手技术不佳,该代码还是有小bug,如有错误,请指出,我会改进