线性表的顺序实现

线性表的结构和相关函数定义如下：

头文件和一些初始定义：

#include <stdio.h> #include <stdlib.h> #define MAXSIZE 100 typedef int datatype;//不一定是要int类型，这样写方便改动时不需要大的操作，直接改动这里

结构体的定义：

typedef struct{ datatype a[MAXSIZE];//创建一个datatype类型的数组 int size; //坐标，便于标明位置 }sequence_list;

初始化顺序表：

void initseqlist(sequence_list *L) { L->size=0; }

输入顺序表元素：

void input(sequence_list *L) { datatype x; initseqlist(L); printf("请输入一组数据，以0做为结束符：\n"); scanf("%d",&x); while(x){ L->a[L->size++]=x;//先将x存入L->a【0】中，然后size+1，往后一位 scanf("%d",&x); } }

打印线性表内容：

void print(sequence_list *L) { int i; for(i=0;i<L->size;i++) { printf("%5d",L->a[i]); if((i+1)%10==0) printf("\n") ; } printf("\n"); }

将线性表内容倒置;

void reverse(sequence_list *L) { datatype t; int j,i=0; j=L->size-1; for(i=0;i<j;i++,j--) { t=L->a[i]; L->a[i]=L->a[j]; L->a[j]=t; } }

将线性表L1，偶数部分储存在L2，奇数部分存储在L3中：

void sprit(sequence_list *L1,sequence_list *L2,sequence_list *L3) { int i, j=0, k=0; for (i = 0; i < L1->size; i++) { if (L1->a[i] % 2 == 0) { L3->a[j] = L1->a[i]; ++j; L3->size=j; } else { L2->a[k] = L1->a[i]; ++k; L2->size=k; } } }

统计顺序表中x的个数：

int count(sequence_list *L, int x) { int i,x_num=0; for(i=0;i<L->size;i++) { if(L->a[i]==x) x_num++; } return x_num; }

在保持大小顺序的顺序表中，插入x并保持线性表大小排序不变

void insert(sequence_list *L,int x) { int j; j=L->size-1; while(j>=0&&L->a[j]>x) { L->a[j+1]=L->a[j]; j--; } L->a[j+1]=x; L->size++; }

尽可能快的将线性表的偶数部分放在线性表的右边部分，奇数放在左边部分 时间复杂度为O（n） 原理：从头和尾分别查找偶数和奇数，将头依次遇到的偶数和尾依次遇到的奇数依次对应对换

void partion(sequence_list *L) { int i,j; i=0; j=L->size-1; while(i<j) { if(L->a[i]%2==0) { if(L->a[j]%2!=0) { int temp=L->a[j]; L->a[j]=L->a[i]; L->a[i]=temp; i++; } else j--; } else i++; } }

删除线性表中说有值为x的数据元素： 解法一：用k记录顺序表L中不等于x的元素个数（即需要保存的元素个数）， 边扫描L边统计k，并将不等于x的元素向前放在k位置上，最后修改L的长度。

void delNode1(sequence_list *L,datatype x) { int i,k; k=0; for(i=0;i<L->size;i++) { if(L->a[i]!=x) { k++; L->a[k-1]=L->a[i]; } } L->size=k; }

解法二：用k记录顺序表L中等于x的元素个数，边扫描L边统计K，并将不等 于x的元素前移k个位置，最后修改L的长度。

void delNode2(sequence_list *L,datatype x) { int i,k; k=0; for(i=0;i<L->size;i++) { if(L->a[i]==x) { k++; } else L->a[i-k]=L->a[i]; } L->size=L->size-k; }