一.什么是数据结构
数据结构研究计算机数据间关系
包括数据的逻辑结构和存储结构及其操作
逻辑结构：
集合、线性结构、树形结构、图状结构
存储结构：
顺序存储：将数据结构中各元素按照其逻辑顺序存放于存储器一片连续的存储空间中
如，c中的一维数组，L=（a1，a2，a3，.......）；
链式存储
将数据结构中各元素分布到存储器的不同点，用地址（或链指针）方式建立它们之间的关系
索引存储
散列存储
总结图
二.线性表
线性表是包含诺干数据元素的一个线性序列
三.顺序存储结构
1.特点
不足：对表的插入和删除等运算的时间复杂度较差，不适用于需要频繁插入和删除的功能的要求
四.顺序表的实现
基本框架
step1：创建sqlist.h sqlist.c（实现.h中的函数） test.c（测试代码） 三个文件
step2：sqlist.h存放数据结构中结构体定义、数据运算基本函数的定义
step3：sqlist.c
：vsp 分频显示的文件 分频显示命令
step3.test.c
接下来让每一个.c文件预处理、编译、汇编生成.o文件
gcc -c sqlist.c -o sqlist.o出现了如下问题，这是因为我们这几个都是在.h中定义的，需要在.c中包含.h文件
#include"sqlist.h"
#include<stdio.h>
之后让这两个.o文件进行链接
也可以直接gcc *.c -o test
具体内容
sqlist.c中封装的具体函数代码
sqlink list_create()
7 {
8 //malloc
9 sqlink L;
10 L = (sqlink)malloc(sizeof(sqlist));
11 if(L==NULL)
12 {
13 printf("list malloc failed\n");
14 return L;
15 }
16 //initialize
17 memset(L,0,sizeof(sqlist));
18 L->last=-1;
19
20 //return
21
22 return L;
23 }
24 /*
25 * @ret 0-successed -1-failed
26 * */
27 int list_clear(sqlink L)//线性表清空，返回值为int
28 {
29 if(L ==NULL)
30 return -1;
31 memset(L,0,sizeof(sqlist));
32 L->last=-1;
33
34 return 0;
35 }
test.c
void test_insert();
void test_delete_x();
void test_merge();
void test_purge();
int main (int argc,const char *argv[])
{
test_purge();
//test_merge();
//test_delete_x();
//test_insert();
return 0;
}
void test_insert()
{
sqlink L;
L = list_create();
if(L==NULL)
return ;
list_insert(L,10,0);
list_insert(L,20,0);
list_insert(L,30,0);
list_show(L);
list_delete(L);
return ;
}
其他函数也是这样子写就行
五.函数功能代码实现原理讲解
1.创建链表
sqlink list_create()
{
//malloc
sqlink L;
L = (sqlink)malloc(sizeof(sqlist));
if(L==NULL)
{
printf("list malloc failed\n");
return L;
}
//initialize
memset(L,0,sizeof(sqlist));
L->last=-1;
//return
return L;
}
2..删除链表中元素
step1：判断这个链表是不是空链表，是直接结束
step2：不是空链表就判断要删除的位置是否有效，范围是从0到last
step3：没有问题之后，开始移动链表，删除一个链表的元素其实就是将它后面的元素对它进行覆盖，也就是删除位置及之后的元素依次往前移动
step4：更细last的信息，删除也就是last--；
int list_delete_x(sqlink L,int pos)
125 {
126 if(L->last==-1)
127 {
128 printf("list is empty\n");
129 return -1;
130 }
131 //pos [0,last]
132 if(pos<0||pos>L->last)
133 {
134 printf("pos is invalid\n");
135 return -1;
136 }
137 //move
138 for(int i =pos+1;i<=L->last;i++)
139 {
140 L->data[i-1]=L->data[i];
141 }
142 //updata
143 L->last--;
144 return 0;
145 }
3.删除链表中的重复元素
思路：第一层while循环从第二个i元素（也就是第二个）开始(i=1)到最后一个元素
第二层while循环从第j（i-1，也就是第i个元素前的元素）开始判断是否相等，一直比对到第一个元素（i=0）结束
如果相等调用删除链表元素的封装函数，删除第i元素，之后break跳出第二层while循环，此时i不递增，因为删除链表元素的封装函数是将元素删除后，被删除的元素的后面的元素往前移动，此时第i个元素是一个未进行判断的元素，所以i不递增，重新判断第i个元素是否重复。
如果不相等，j--，一直比对到第一个元素，然后结束第二层while循环，之后i++
这里用j<0来判断是否是进行了删除元素的操作，j<0,说明是没找到重复元素正常跳出第二层while循环，i++；不小于0，说明是进行了删除元素之后使用break跳出的第二层循环。
int list_purge(sqlink L)
164 {
165 int i,j;
166 if(L->last==0) return 0;//如果只有一个元素不进行操作
167 i=1;
168 while(i<=L->last)
169 {
170 j=i-1;
171 while(j>=0)
172 {
173 if(L->data[i]==L->data[j])
174 {
175 list_delete_x(L,i);
176 break;
177 }
178 else
179 {
180 j--;
181 }
182 }
183 if(j<0)
184 {
185 i++;
186 }
187 }
188
189 return 0;
190 }
4.插入链表
int list_insert(sqlink L,data_t value,int pos)//线性表插入元素
{
int i;
//先看表满没有，其次参数是否合法，之后元素移动,从后往前移动，最后存入新值，更新last
//full
if(L->last==N-1)
{
printf("list is full\n");
return -1;
}
//check para 0<=pos<=lsat+1
if(pos <0||pos>L->last+1)
{
printf("pos is invalid\n");
return -1;
}
//move
for(i=L->last;i>=pos;i--)
{
L->data[i+1]=L->data[i];
}
//update value last
L->data[pos]=value;
L->last++;
return 0;
}
5.清空链表
int list_clear(sqlink L)//线性表清空，返回值为int
{
if(L ==NULL)
return -1;
memset(L,0,sizeof(sqlist));
L->last=-1;
return 0;
}
6.释放链表空间
int list_delete(sqlink L)
{
if(L==NULL)
return -1;
free(L);
L=NULL;
return 0;
}
7.判断链表是否为空
int list_empty(sqlink L)//判断线性表是否是空~
{
if(L->last==-1)
{
return 1;
}
else
return 0;
}
8.计算链表长度
int list_length(sqlink L)//求线性表的长度
{
if(L==NULL)
return -1;
return L->last+1;
}
9.输出链表元素
int list_show(sqlink L)
{
int i;
if(L==NULL)
{
return -1;
}
if(L->last==-1)
{
printf("list is empty\n");
}
for(i=0;i<=L->last;i++)
{
printf("%d ",L->data[i]);
}
puts("");//输出空格并换
return 0;
}
10.查看链表是否有某个元素
int list_locate(sqlink L,data_t value)//查找value这个元素是否在表中
{
int i;
for(i=0;i<=L->last;i++)
{
if(L->data[i]==value)
return i;
}
return -1;
}
11.合并两个链表
int list_merge(sqlink L1,sqlink L2)
{
int i=0;
int ret;
while(i<=L2->last)//一个个循环L2的元素
{
ret=list_locate(L1,L2->data[i]);//查看L1中是否有这个元素
if(ret==-1)//没有这个元素
{
if(list_insert(L1,L2->data[i],L1->last+1)==-1)//插入到L1的后面
return -1;
}
i++;
}
return 0;
}