线性表之顺序表

一、线性表是包含若干元素的一个线性序序列

        线性表L可用二元组形式描述：L=(D,R) 既线性表L包含数据元素集合D和关系集合R线性表的特征：对非空表，a0是表头，无前驱；

                        an-1是表尾，无后继；

                        其它的每个元素ai有且仅有一个直接前驱ai-1，和一个直接后继ai+1。

二、顺序存储结构的特点

        逻辑上相邻的元素ai,ai+1,其存储位置也是相邻的

        对数据元素ai的存取为随机存器或者按地址存取

        存储密度高

三、存储结构的不足：

        要求系统提供一片较大的连续存储空间。

        插入、删除等运算耗时，且存在元素在存储器中成片移动的现象。

        对表的插入和删除等运算的时间复杂度较差。

        在C语言中，可借助于一维数组类型来描述线性表的顺序存储结构

#define N 100
typedef int data_t
typedef struct
{  data_t data[N];//表的存储空间int last;
}  sqlist,*sqlink;

四、线性表的基本运算

设线性表L=(a0,a1,......,an-1)，对L的基本运算由：

建立一个空表：list_create(L)

置空表：list_clear(L)

判断表是否为空：list_empty(L)。若表为空，返回值为1，否则返回0

求表长：length(L)

取表中某一个元素：GetList(L,i)，即ai。要求0≤i≤length(L)-1

定位运算：Locate(L,x)。确定元素x在表L中的位置（或序号）

插入：linsert(L,x,i)。将元素x插入到表L中第i个元素ai之前，且表长+1。

删除：Delete(L)。删除表L中第i个元素ai，且表长减1，要求0≤i≤n-1。

线性表的合并：一次取表Lb中的bi(i=0,1,......,n-1)，若bi不属于，则将其插入表La中。

清除线性表中重复的元素：对当前表中的每一个ai(0≤i≤n-2)，依次与aj(i+1≤j≤n-1)比较，若与ai相等，则删除之。

多文件程序

main.c

#include <stdio.h>
#include "list.h"int main()
{sqlink L;L = list_create();return 0;		
}

 list.c

#include <stdio.h>
#include "list.h"sqlink list_create(){return 0;		
}
int lis_clrate(sqlink L){return 0;		
}
int list_empty(sqlink L){return 0;		
}
int list_length(sqlink L){return 0;		
}
int list_locate(sqlink L, data_t value){return 0;		
}
int list_insert(sqlink L, data_t value, int pos){return 0;		
}

 list.h

typedef int data_t;
#define N 128typedef struct {data_t data[N];int last;
}sqlist, *sqlink;sqlink list_create();
int list_clreate(sqlink L);
int list_empty(sqlink L);
int list_length(sqlink L);
int list_locate(sqlink L, data_t value);
int list_insert(sqlink L, data_t value, int pos);

多步执行

gcc -c list.c -o list.o

gcc -c main.c -o main.o

gcc list.o main.o -o test

一步执行

gcc *,c -o test

main.c

#include <stdio.h>
#include "list.h"void test_purge();
void test_insert();
void test_delete();
void test_merge();int main()
{//test_insert();
//	test_delete();//test_merge();//线性表合并test_purge();//去除线性表中的重复元素return 0;
}void test_purge(){sqlink L;L = list_create();if(L == NULL)return;list_insert(L, 1, 0);list_insert(L, 1, 0);list_insert(L, 1, 0);list_insert(L, 2, 0);list_insert(L, 3, 0);list_insert(L, 4, 0);list_insert(L, 4, 0);list_insert(L, 5, 0);list_insert(L, 6, 0);list_show(L);list_purge(L);list_show(L);list_free(L);
}void test_merge(){sqlink L1,L2;L1 = list_create();if(L1 == NULL)return;L2 = list_create();if(L2 == NULL)return;list_insert(L1, 1, 0);list_insert(L1, 2, 0);list_insert(L1, 3, 0);list_insert(L1, 4, 0);list_insert(L2, 4, 0);list_insert(L2, 5, 0);list_insert(L2, 6, 0);list_insert(L2, 7, 0);list_show(L1);list_show(L2);printf("**************\n");list_merge(L1, L2);list_show(L1);list_show(L2);
}void test_delete(){sqlink L;L = list_create();if(L == NULL)return;list_insert(L, 10, 0);list_insert(L, 60, 0);list_insert(L, 40, 0);list_insert(L, 50, 0);list_insert(L, 70, 0);list_insert(L, 80, 0);list_insert(L, 90, 0);list_show(L);list_delete(L, 0);list_show(L);
}
void test_insert(){sqlink L;L = list_create();if(L == NULL)return;list_insert(L, 10, 0);list_insert(L, 60, 0);list_insert(L, 40, 0);list_insert(L, 50, 0);list_insert(L, 70, 0);list_insert(L, 80, 0);list_insert(L, 90, 0);list_show(L);list_insert(L, 90, 0);list_show(L);
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "list.h"sqlink list_create(){//mallocsqlink L;L = malloc(sizeof(sqlist));if(L == NULL){printf("list malloc failed\n");return L;}//initializememset(L, 0, sizeof(sqlist));L->last = -1;//returnreturn L;	
}int list_free(sqlink L){if(L == NULL)return -1;free(L);L = NULL;return 0;
}
/** @ret 0-success 1-failed* */
int lis_clear(sqlink L){if(L ==NULL)return -1;memset(L, 0, sizeof(sqlist));L->last = -1;return 0;		
}
/**list_empty:Is list empty ?*para L:list *@ret 1--empty 0--not empty* */
int list_empty(sqlink L){if (L->last == -1)return 1;elsereturn 0;	
}
int list_length(sqlink L){if(L == NULL)return -1;return (L->last+1);		
}
int list_locate(sqlink L, data_t value){int i;for(i = 0; i <= L->last; i++){if(L->data[i] == value)return i;}return -1;		
}
int list_insert(sqlink L, data_t value, int pos){int i;//fullif(L->last == N-1){printf("list is full\n");return -1;}//check para 0≤pos≤last+1 [0,last+1]if((pos < 0) || (pos >L->last+1)){printf("Pos is invalid\n");return -1;}//movefor(i = L->last; i>=pos; i--){L->data[i+1] = L->data[i];}//update value lastL->data[pos] = value;L->last++;return 0;		
}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;}int list_delete(sqlink L, int pos){int i;//fullif(L->last == N-1){printf("list is full\n");return -1;}//pos [0, last]if((pos < 0) || (pos > L->last)){printf("Pos is invalid\n");return -1;}//move [pos+1, last]for(i = pos+1; i <= L->last; i++){L->data[i-1] = L->data[i];}//updateL->last--;return 0;		
}
int list_merge(sqlink L1, sqlink L2){int i = 0;int ret;while(i <= L2->last){ret = list_locate(L1, L2->data[i]);if(ret == -1){if(list_insert(L1, L2->data[i], L1->last+1) == -1)return -1;}i++;}return 0;
}
int list_purge(sqlink L){int i;int j;if (L->last == 0)return 0;i = 1;while (i <= L->last) {j = i-1;while (j >= 0) {if (L->data[i] == L->data[j]) {list_delete(L, i);break;} else {j--;}}if ( j < 0) {i++;}}return 0;
}

 list.h

typedef int data_t;
#define N 128typedef struct {data_t data[N];int last;		
}sqlist, *sqlink;sqlink list_create();
int list_clear(sqlink L);
int list_free(sqlink L);
int list_empty(sqlink L);
int list_length(sqlink L);
int list_locate(sqlink L, data_t value);
int list_insert(sqlink L, data_t value, int pos);
int list_delete(sqlink L, int pos);
int list_merge(sqlink L, sqlink L2);
int list_purge(sqlink L);
int list_show(sqlink L);