当前位置：首页 > backend >正文

0722 数据结构顺序表

backend 2025/7/23 7:16:41

Part 1.顺序表的代码

一.顺序表的内存申请

head.h:
typedef int datatype;typedef struct sqlist
{//数据元素datatype data[MAXSIZE];//顺序表长度int len;}*sqlist;
//*sqlist的作用:
//sqlist:struct Sqlist *
sqlist create();head.c:
sqlist create()
{sqlist list =(sqlist)malloc(sizeof(struct sqlist));//申请堆区空间由指针list接收if(NULL == list)return NULL;//数据表元素清零bzero(list->data,sizeof(list->data));//顺序表长度清零list->len = 0;return list;
}main.c:
sqlist list = create();

二.顺序表尾插+遍历

head.h:
int output(sqlist list);
int insert(sqlist list,datatype element);head.c:
//插入函数
int insert (sqlist list,datatype element)
{if(NULL == list || list->len == MAXSIZE){	printf("顺序表满了\n");return Faluse;}//插入数据list->data[list->len] = element;//顺序表长度自增list->len++;return Success;
}
//遍历函数
int output(sqlist list)
{if(NULL == list || list->len == 0){	printf("顺序表为空\n");return Faluse;}for(int i = 0;i < list->len; i++){printf("%d\t",list->data[i]);}printf("\n");return Success;
}main.c：
for(int i = 0; i < MAXSIZE; i++){scanf("%d",&element);insert(list,element);}output(list);

三.顺序表尾删

head.h:
int delete_rear(sqlist list);head.c:
int delete_rear(sqlist list)
{if(NULL == list || list->len == 0){	printf("顺序表为空\n");return Faluse;}list->len--;return Success;
}main.c:
delete_rear(list);

四.顺序表按下表插入

head.h:
int index_insert(sqlist list,int index, datatype element);head.c:
int index_insert(sqlist list,int index, datatype element)
{if(NULL == list || list->len == MAXSIZE || index < 0 || index >= list->len){	printf("error\n");return Faluse;}list->len++;for (int i = list->len; i >index; i--)//将要加数的下标的表值都往后移{list->data[i] = list->data[i-1];}list->data[index] = element;return Success;
}main.c:
index_insert(list,1,9);

五.顺序表按下表删除

head.h:
int index_delete(sqlist list,int index);head.c:
int index_delete(sqlist list,int index)
{if(NULL == list || list->len == 0 || index < 0 || index >= list->len){	printf("error\n");return Faluse;}for (int i = index; i < list->len; i++)//全部前移{list->data[i] = list->data[i+1];}list->len--;return Success;
}main.c：
index_delete(list,2);

六.顺序表按下表修改

head.h:
int index_change(sqlist list,int index,datatype element);head.c:
int index_change(sqlist list,int index, datatype element)
{if(NULL == list || list->len == 0 || index < 0 || index >= list->len){	printf("error\n");return Faluse;}list->data[index] = element;//将下标对应的表值改为输入的值return Success;
}main.c:
index_change(list,2,5);

七.顺序表按下表查找

head.h:
int index_select(sqlist list,int index);head.c:
int index_select(sqlist list,int index)
{if(NULL == list || list->len == 0 || index < 0 || index >= list->len){	printf("error\n");return Faluse;}printf("%d\n",list->data[index]);//输出下标的值return Success;
}main.c:
index_select(list,3);

八.顺序表按元素删除

head.h:
int element_delete(sqlist list,datatype element);head.c:
int element_delete(sqlist list,datatype element)
{if(NULL == list || list->len == 0){	printf("error\n");return Faluse;}int index = 0;for(int j = 0; j < list->len; j++){if(list->data[j] == element)//找到对应值的下标，进行下标删除{index = j;	for(int i = index; i < list->len; i++){list->data[i] = list->data[i+1];}list->len--;}}return Success;
}main.c；
element_delete(list,5);

九.顺序表按元素查找

head.h:
int element_select(sqlist list,datatype element);head.c:
int element_select(sqlist list,datatype element)
{if(NULL == list || list->len == 0){	printf("error\n");return Faluse;}int index = 0;for(int j = 0; j < list->len; j++){if(list->data[j] == element)//找到对应元素下标并输出{printf("%d\n",j);}}return Success;
}main.c：
element_select(list,9);

十.顺序表按元素修

head.h:
int element_change(sqlist list,datatype element,datatype elementchange);head.c:
int element_change(sqlist list,datatype element,datatype elementchange)
{if(NULL == list || list->len == 0){	printf("error\n");return Faluse;}int index = 0;for(int j = 0; j < list->len; j++){if(list->data[j] == element)//循环寻找下标，并赋值{list->data[j] = elementchange;}}return Success;
}main.c：
element_change(list,9,5);

十一.顺序表去重

head.h:
int D_repetition_rate(sqlist list);head.c:
int D_repetition_rate(sqlist list)
{if(NULL == list || list->len == 0){	printf("error\n");return Faluse;}int index = 0;for(int i = 0; i < list->len; i++){for(int j = i + 1; j < list->len; j++)//每次循环与循环首进行比较{if(list->data[i] == list->data[j])//找到相同的值，调用下标删除{	index = j;	for(int i = index; i < list->len; i++){list->data[i] = list->data[i+1];}list->len--;j--;//往前走一位}}}return Success;
}main.c：
D_repetition_rate(list);

十二.顺序表排序

head.h:
int paixu(sqlist list);head.c:
int paixu(sqlist list)
{if(NULL == list || list->len == 0){	printf("error\n");return Faluse;}for(int i = 1; i < list->len; i++)//冒泡排序{for(int j = 0; j < list->len-i; j++){if(list->data[j] >= list->data[j+1]){		int x = list->data[j];list->data[j] = list->data[j+1];list->data[j+1] = x;}}}return Success;
}main.c：
paixu(list);

Part 2.整理

一.数据结构

1.逻辑结构

a.集合结构

元素之间没有关系

b.线性结构

元素之间有一对一的关系

c.树形结构

元素之间有一对多关系

d.图形结构

元素之间有多对多的关系

2.存储结构

a.顺序存储

使用一段连续的空间存储多个相同类型的数据元素

b.链式存储

使用任意一段空间存储多个相同类型的数据元素

a和b的区别

两种方式都是逻辑上相连，但是链式存储物理空间上没有相连

c.索引结构

用索引方法和数据表实现查找的结构

d.散列存储

使用哈希存储的一直存储方式

二.时间复杂度

T(n) = O(f(n))
T：时间
n：问题的规模
O：大O阶，渐进符

无循环函数
int a = 0; 1
printf("%d",a); 1
T(n) =O(1)
for循环
for(int i = 0; i<n; i++) n+1
{
  printf("%d",i); n
}
T(n) =O(n)
嵌套for循环
for(int i = 0; i<n; i++) n+1
{
  for(int j = 0; j<n; j++) n*(n+1)
        {
                printf("%d",i); n*n
        }
}
T(n) =O(n^2)