- 1 SeqList.c
- 1.1 线性表特点
- 1.2 线性表初始化
- 1.3 从线性表末尾添加元素
- 1.4 从线性表表首添加元素
- 1.5 列举线性表
- 1.6 从线性表末尾删除元素
- 1.7 从线性表表首删除元素
- 1.8 在线性表指定位置插入元素
- 1.9 查找元素
- 1.20 返回线性表长度
- 1.21 删除线性表指定位置元素
- 1.22 删除线性表指定值
- 1.23 对线性表排序
- 1.24 清除线性表
- 2 SeqList.h
- 3 main.c
线性表是在连续空间中存储的同类型元素。
除了首尾元素只有后继和前驱，中间的每个元素都有前驱和后继，因此知道首元素存储的位置，其它元素的位置迅速搜索到。loc(ai)=loc(a0)+(i-0)*(数据类型字节）。小明一班20人按照名次住同一层，每人一个房间，且房间相连。小明为第一名，宿舍号为123，小亮为第五名，他的房间号为123+（5-1）=127。
线性表优缺点：
线性表搜索元素时间复杂度为O(1)，但是在插入、删除元素时需要挪动元素，最差的时间复杂的为O(n)。除此之外，线性表需要要占据连续的空间。
线性表有多个属性，因此用结构体初始化。线性表的属性包括数组、容量、元素数量。数组用来存储元素，容量表示线性表最大储存元素的数量，元素数量是实际储存元素数量。
可以静态初始化，也可以动态初始化。静态初始化直接在栈空间确定一个连续的空间。动态初始化是通过指定类型指针在堆空间动态分配内存，内存的大小可以根据需要再进行调整，使用后要手动释放内存。
因为要对线性表内容调整，因此输入参数为线性表地址。a. 判断线性表是否满员。b. 如果线性表未满员，取出线性表元素数量，在最后一个元素添加到表中，同时元素数量+1。
1.4 从线性表表首添加元素a.判断线性表是否满员。b.上一判断不成立，从后n-1向前遍历到0，每个元素都向后挪动一个位置，空出第一个元素。c. 把输入元素放在第一个位置上，同时元素数量+1。
1.5 列举线性表根据元素数量遍历线性表，打印每个元素的数值。
1.6 从线性表末尾删除元素线性表元素数量减一，这样最后一个元素无效。
1.7 从线性表表首删除元素a. 从第二个元素到最后一个元素，每个元素向前挪动一位。b.线性表元素数量减一。
1.8 在线性表指定位置插入元素a. 判断位置是否合理。b.上一条件满足，指定位置上及之后的元素都向后挪动一个位置。b.把插入元素放在指定位置。d. 线性表元素数量+1。
1.9 查找元素遍历线性表，判断每个元素是否跟查找元素是否相同。如果查找到，就返回对应元素的下标；反之，返回-1。
1.20 返回线性表长度返回线性表长度。
1.21 删除线性表指定位置元素a.线性表指定位置之后的数据都向前挪动一位。b. 线性表元素数量-1。
1.22 删除线性表指定值a. 用24的函数判断元素在线性表的位置。b.如果元素在线性表中，用26函数删除元素。
1.23 对线性表排序用冒泡法对数据排序。
1.24 清除线性表a.释放堆空间。b.指针为空值。
总结：通过以上代码，可以发现指针和循环用的多。a.用指针对线性表元素修改。遍历主要用在罗列、删除、插入、查找中。b. 线性表根据下标查找元素非常方便，但是删除、查找比较麻烦，还需要连续的存储空间。链表的优缺点与线性表正好相反。数据量不大，线性表可以考虑。
//
// SeqList.c
// 21days study C language
//
// Created by ls .
// Copyright © 2022 LSC001. All rights reserved.
//
#include "SeqList.h"
void InitSeqList(SeqList *list)
{
list->base = (ElemType *)malloc(sizeof(ElemType)*SEQLIST_INIT_SIZE); // 线性表开辟空间
assert(list->base != NULL); // 判断空间是否开辟成功
list->capacity = SEQLIST_INIT_SIZE;
list->size = 0;
}
void push_back(SeqList *list,ElemType item)
{
if (list->size >= list->capacity)
{
printf("空间已满，不能插入！");
return;
}
else
{
list->base[list->size]=item;
list->size++;
}
}
void push_front(SeqList *list,ElemType item)
{
int i;
if (list->size>=list->capacity)
{
printf("空间已满，不能插入！");
return;
}
i=list->size;
while(i>0)
{
list->base[i]=list->base[i-1];
i--;
}
list->base[0]=item;
list->size++;
}
void show_list_(SeqList list)
{
int i = 0;
for (i=0;i<list.size;++i)
{
printf("%d ",list.base[i]);
}
}
void pop_back(SeqList *list)
{
list->size = list->size-1;
}
void pop_front(SeqList *list)
{
int i ;
for(i=1;i<list->size;++i)
{
list->base[i-1]=list->base[i];
}
list->size = list->size-1;
}
void insert_pos(SeqList *list,int pos,ElemType item)
{
if(pos>list->size)
{
list->base[list->size] = item;
}else
{
int i;
for(i=list->size-1;i>=pos-1;--i)
{
list->base[i+1]=list->base[i];
}
list->base[pos-1] = item;
}
list->size = list->size+1;
}
int find(SeqList list, ElemType item)
{
int i,j=-1;
for(i=0;i < list.size;++i)
{
if (item == list.base[i])
{
j=i;
break;
}
}
return j;
}
int length(SeqList list)
{
return list.size;
}
void delete_pos(SeqList *list,int pos)
{
int i ;
if(pos<0)
{
printf("pos数据不能为负数");
}else if(pos >= list->size)
{
list->size--;
}else
{
for(i = pos;i<list->size;i++)
{
list->base[i-1] = list->base[i];
}
list->size--;
}
}
void delete_value_(SeqList *list,ElemType value)
{
if(-1 == find(*list, value))
{
printf("NO VALUE IN SeqList");
}
else
{
int i = find(*list,value);
delete_pos(list,i+1);
}
}
void sort(SeqList *list)
{
int len = list->size;
int i,j;
ElemType tmp;
for(i=0;i<len-1;++i)
{
for(j=0;j<len-1-i;++j)
{
if(list->base[j] > list->base[j+1])
{
tmp = list->base[j];
list->base[j] = list->base[j+1];
list->base[j+1] = tmp;
}
}
}
}
void reverse(SeqList *list)
{
int i,j;
ElemType tmp;
for(i=0,j=list->size-1;i<=(list->size)/2;i++,--j)
{
tmp = list->base[i];
list->base[i] = list->base[j];
list->base[j] = tmp;
}
}
void clear_(SeqList *list)
{
list->size = 0;
}
void destroy_(SeqList *list)
{
free(list);
list=NULL;
}
//
// SeqList.h
// 21days study C language
//
// Created by ls.
// Copyright © 2022 LSC001. All rights reserved.
//
#ifndef SeqList_h
#define SeqList_h
#include #include "SeqList.h"
int main()
{
SeqList mylist; // 结构体变量
InitSeqList(&mylist); // 初始化线性表
ElemType item; // 线性表插入或删除的数值
int pos; // 位置信息
int select=1; // 对线性表 *** 作的初始化数值
while(select)
{
printf("\n");
printf("*********************************************\n");
printf("* [1] push_back [2] push_front *\n");
printf("* [3] show_list_ [4] pop_back *\n");
printf("* [5] pop_front [6] insert_pos *\n");
printf("* [7] find [8] length *\n");
printf("* [9] delete_pos [10] delete_value *\n");
printf("* [11] sort [12] reverse *\n");
printf("* [13] clear_ [14] destroy *\n");
printf("* [15] quit_system *\n");
printf("*********************************************\n");
printf("请选择：-> ");
scanf("%d",&select);
if(0 == select) break;
switch (select) {
case 1:
{
printf("请选择输入 item 数值:");
scanf("%d",&item);
push_back(&mylist,item);
show_list_(mylist);
break;
}
case 2:
{
printf("请选择输入 item 数值:");
scanf("%d",&item);
push_front(&mylist,item);
show_list_(mylist);
break;
}
case 3:
{
show_list_(mylist);
break;
}
case 4:
{
pop_back(&mylist);
show_list_(mylist);
break;
}
case 5:
{
pop_front(&mylist);
show_list_(mylist);
break;
}
case 6:
{
printf("请选择输入 pos,item 数值:\n");
scanf("%d,%d",&pos,&item);
insert_pos(&mylist,pos,item);
show_list_(mylist);
break;
}
case 7:
{
printf("请选择输入item 数值:\n");
scanf("%d",&item);
int i = find(mylist,item);
printf("item的下标为:%d\n",i);
break;
}
case 8:
{
int len = length(mylist);
printf("list.size：%d\n",len);
break;
}
case 9:
{
printf("请选择输入pos 数值:\n");
scanf("%d",&pos);
delete_pos(&mylist,pos);
show_list_(mylist);
break;
}
case 10:
{
int value;
printf("请选择输入value 数值:\n");
scanf("%d",&value);
delete_value_(&mylist,value);
break;
}
case 11:
{
sort(&mylist);
show_list_(mylist);
break;
}
case 12:
{
reverse(&mylist);
show_list_(mylist);
break;
}
case 13:
{
clear_(&mylist);
show_list_(mylist);
break;
}
case 14:
{
destroy_(&mylist);
break;
}
case 15:
{
break;
}
default:
printf("输入错误，请重新输入。");
break;
}
}
return 0;
}
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）