顺序表(线性表的顺序存储结构)及C语言实现

程序员文章站 2022-05-21 11:49:05

...

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 20
#define initSize 10
typedef int ElemType;
typedef struct{
	ElemType *data;
	int length;
}SeqList;

SeqList initList(){
	SeqList L;
	L.data=(ElemType*)malloc(sizeof(ElemType)*initSize);
	L.length=0;
	return L;
}

void display(SeqList list){
	int i;
	for(i=0;i<list.length;i++){
		printf("%d\n",list.data[i]);
	}
}
//插入
SeqList insert(SeqList L,int i,ElemType e){
	int j;
	if(i<1||i>L.length+1){
		return L;
	}
	if(L.length>initSize){
		printf("数据满了");
		return L;
	}
	
	for(j = L.length;j>=i;j--){
		L.data[j]=L.data[j-1];
	}
	L.data[i-1]=e;
	L.length++;
	return L;
}
//删除
SeqList delList(SeqList L,int i,ElemType e){
	int j;
	if(i<1||i>L.length){
		return L;
	}
	for(j=i;j<L.length;j++){
		L.data[j-1]=L.data[j];
	}
	L.length--;
	return L;
}
//查询
int select(SeqList L,ElemType e){
	int i;
	for(i=0;i<L.length;i++){
		if(L.data[i]==e){
			return i+1;
		}
	}
	return -1;
}
//更新
SeqList update(SeqList L,int i ,ElemType e){
	int j;
	if(i<1||i>L.length+1){
		return L;
	}
	for(j=0;j<L.length;j++){
		L.data[i-1]=e;
	}
	return L;
}
int main(void)
{	
	int i;
	SeqList list = initList();

	for(i =1;i<=6;i++){
		list.data[i-1]=i;
		list.length++;
	}
	printf("原始数据\n");
	display(list);
	printf("在第三个位置插入数据50\n");
	list = insert(list,3,50);
	display(list);
	printf("在第三个位置删除数据50\n");
	list = delList(list,3,50);
	display(list);
	printf("查找5元素%d",select(list,5));

	printf("在第五个位置数据为50\n");
	list = update(list,5,50);
	display(list);
	getchar();
	return 0;
}

参考https://www.jianshu.com/p/f4cca5ce055a
我们知道常数项对函数的增长速度影响并不大，所以当 T(n) = c，c 为一个常数的时候，我们说这个算法的时间复杂度为 O(1)；如果 T(n) 不等于一个常数项时，直接将常数项省略。

比如
第一个 Hello, World 的例子中 T(n) = 2，所以我们说那个函数(算法)的时间复杂度为 O(1)。
T(n) = n + 29，此时时间复杂度为 O(n)。

我们知道高次项对于函数的增长速度的影响是最大的。n^3 的增长速度是远超 n^2 的，同时 n^2 的增长速度是远超 n 的。同时因为要求的精度不高，所以我们直接忽略低此项。

比如
T(n) = n^3 + n^2 + 29，此时时间复杂度为 O(n^3)。

因为函数的阶数对函数的增长速度的影响是最显著的，所以我们忽略与最高阶相乘的常数。

比如
T(n) = 3n^3，此时时间复杂度为 O(n^3)。

综合起来：如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))。为了方便描述，下文称此为大O推导法。

作者：raymondCaptain
链接：https://www.jianshu.com/p/f4cca5ce055a
来源：简书
简书著作权归作者所有，任何形式的转载都请联系作者获得授权并注明出处。

王道数据结构书第18页的一些习题

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#define MAXSIZE 20
#define initSize 30
typedef int ElemType;
typedef struct{
	ElemType *data;
	int length;
}SeqList;

SeqList initList(){
	SeqList L;
	L.data=(ElemType*)malloc(sizeof(ElemType)*initSize);
	L.length=0;
	return L;
}

void display(SeqList list){
	int i;
	for(i=0;i<list.length;i++){
		printf("%d\n",list.data[i]);
	}
}
//插入
SeqList insert(SeqList L,int i,ElemType e){
	int j;
	if(i<1||i>L.length+1){
		return L;
	}
	if(L.length>initSize){
		printf("数据满了");
		return L;
	}
	
	for(j = L.length;j>=i;j--){
		L.data[j]=L.data[j-1];
	}
	L.data[i-1]=e;
	L.length++;
	return L;
}
//删除
SeqList delList(SeqList L,int i,ElemType e){
	int j;
	if(i<1||i>L.length){
		return L;
	}
	for(j=i;j<L.length;j++){
		L.data[j-1]=L.data[j];
	}
	L.length--;
	return L;
}
//查询
int select(SeqList L,ElemType e){
	int i;
	for(i=0;i<L.length;i++){
		if(L.data[i]==e){
			return i+1;
		}
	}
	return -1;
}
//更新
SeqList update(SeqList L,int i ,ElemType e){
	int j;
	if(i<1||i>L.length+1){
		return L;
	}
	for(j=0;j<L.length;j++){
		L.data[i-1]=e;
	}
	return L;
}
//第一题
SeqList del_min(SeqList L){
	int i ,pos=0;
	ElemType min;
	if(L.length==0){
		return L;
	}
	min = L.data[0];
	for(i=0;i<L.length;i++){
		if (L.data[i]<min){
			min = L.data[i];
			pos = i;
		}
	}
	L.data[pos]=L.data[L.length-1];
	return L;
	
}
//逆置
SeqList reverse(SeqList L){
	ElemType temp;
	int i ;
	for(i=0;i<L.length/2;i++){
		temp = L.data[i];
		L.data[i]=L.data[L.length-1-i];
		L.data[L.length-1-i]=temp;
	}
	return L;
}
//第三题
SeqList del_k(SeqList L,ElemType x){
	int k=0;
	int i;
	for (i=0;i<L.length;i++){
		if (L.data[i]!=x){
			L.data[k]=L.data[i];
			k++;
		}
	}
	L.length=k;
	return L;
}
//第四题
SeqList del_st(SeqList L,ElemType s,ElemType t){
	int i,j,k=0;
	if(s>t){
		return L;
	}
	if (L.length==0){
		printf("顺序表为空");
		return L;
	}
	for (i=0;i<L.length;i++){
		if(L.data[i]>s&&L.data[i]<t){
			
			k++;
		}else{
			L.data[i-k]=L.data[i];

		}
	}
	L.length-=k;
	return L;
}
//去掉相同
SeqList del_same(SeqList L){
	int i=0;
	int j=1;
	for(;j<L.length;j++){
		if(L.data[i]!=L.data[j]){
			i++;
			L.data[i]=L.data[j];
		}
	}
	L.length=i+1;
	return L;
}
//两个顺序表排序
SeqList sortSeq(SeqList L1,SeqList L2,SeqList L3){
	int i=0,j=0,k=0;
	if(L1.length+L2.length>=initSize){
		return L1;
	}
	while(i<L1.length&&j<L2.length){
		if(L1.data[i]<L2.data[j]){
			L3.data[k++]=L1.data[i++];
		}else{
			L3.data[k++]=L2.data[j++];
		}
	}
	while(i<L1.length){
		L3.data[k++]=L1.data[i++];
	}
	while(j<L2.length){
		L3.data[k++]=L2.data[j++];
	}
	L3.length=k;
	printf("L3length%d,k=%d",L3.length,k);
	return L3;
}
//第九题
SeqList findXandExchange(SeqList L, ElemType x){
	int left =0;
	int right = L.length-1;
	int mid;
	int i;
	ElemType temp;
	while(left<=right){
		mid=(left+right)/2;
		if(L.data[mid]==x){
			break;
		}
		if (L.data[mid]<x){
		left = mid+1;
		}else{
		right = mid-1;
		}
	}
	if(L.data[mid]==x&&mid!=L.length-1){
		temp = L.data[mid];
		L.data[mid]=L.data[mid+1];
		L.data[mid+1]=temp;
	}
	if(left>right){
		for(i=L.length-1;i>right;i--){
			L.data[i+1]=L.data[i];
		}
		L.data[i+1]=x;
		L.length++;
	}
	return L;
}

char * reverseChar(char c[],int left,int right){
	int i ,j;
	char temp;
	int length = strlen(c);
	i = left;
	j= right;
	
	for(;i<(right+left)/2;i++,j--){
		temp = c[i];
		c[i]=c[j];
		c[j]=temp;

	}
	return c;
}
char * converse(char c[],int length,int p ){
	reverseChar(c,0,p-1);
	printf("第一次%s",c);
	reverseChar(c,p,length-1);
	printf("第2次%s",c);
	reverseChar(c,0,length-1);
	printf("第3次%s",c);
	return c;
}
void test(int t){
	t=5;
}
int main(void)
{	
	int i;
	char str[]= "abcdefgh";
	int t=10;
	
	SeqList list1 = initList();
	SeqList list2 = initList();
	SeqList list3 = initList();
	int left = 0;
	int right = strlen(str);
	int mid = (left + right)/2;
	char temp;
	printf("%d",t);
	printf("test\n");
	converse(str,right,3);
	printf("\n");
	
	/*for (;left<mid;left++,right--){
		temp = str[left];
		str[left]= str[right];
		str[right]=temp;
	}*/
	/*while(left<=right){
		temp = str[left];
		str[left]= str[right];
		str[right]=temp;
		left++;
		right--;
	}*/
	for (i=0;i<=mid;i++){
		temp = str[i];
		str[i]=str[right-i];
		str[right-i] = temp;
	}
	printf(str);

	for(i =1;i<=10;i++){
		list1.data[i-1]=i;
		list1.length++;
	}
	for(i =1;i<=10;i++){
		list2.data[i-1]=i*2;
		list2.length++;
	}
	printf("原始数据1\n");
	display(list1);
	printf("原始数据2\n");
	display(list2);
	printf("第九题");
	list2= findXandExchange(list2,11);
	display(list2);
	//printf("排序数据3\n");
	//list3 = sortSeq(list1,list2,list3);
	//display(list3);
	//printf("在第三个位置插入数据50\n");
	//list = insert(list,2,2);
	//list = insert(list,3,2);
	//list = insert(list,7,5);
	//display(list);
	//printf("在第三个位置删除数据50\n");
	//list = delList(list,3,50);
	//display(list);
	//printf("查找5元素%d",select(list,5));

	//printf("在第五个位置数据为50\n");
	//list = update(list,5,50);
	//display(list);


	/*printf("第一题\n");
	list = del_min(list);
	display(list);
	printf("第二题逆置\n");
	list = reverse(list);
	display(list);*/
	//printf("第三题\n");
	//list = del_k(list,6);
	//display(list);
	//printf("第四题st\n");
	//list = del_st(list,2,5);
	//display(list);
	/*printf("第五题same\n");
	list = del_same(list);
	display(list);*/
	getchar();
	return 0;
}

上一篇： C++：从n个字符中去m个字符的组合【菊厂面试】

下一篇： php发送邮件的问题详解_PHP教程

顺序表(线性表的顺序存储结构)及C语言实现

c语言数据结构之线性表的顺序存储结构

python数据结构之线性表的顺序存储结构

python数据结构学习之实现线性表的顺序

JS实现线性表的顺序表示方法示例【经典数据结构】

C++语言------顺序表实现,用动态数组的方法

C语言数据结构之线性表的链式存储结构

Go语言实现顺序存储的线性表实例

C语言顺序表的实现（动态）

数据结构——线性表的顺序存储结构

数据结构之---C语言实现串的顺序存储

顺序表(线性表的顺序存储结构)及C语言实现

c语言数据结构之线性表的顺序存储结构

python数据结构之线性表的顺序存储结构

python数据结构学习之实现线性表的顺序

JS实现线性表的顺序表示方法示例【经典数据结构】

C++语言------顺序表实现,用动态数组的方法

C语言数据结构之线性表的链式存储结构

Go语言实现顺序存储的线性表实例

C语言 顺序表的实现 （动态）

数据结构——线性表的顺序存储结构

数据结构之---C语言实现串的顺序存储

C语言顺序表的实现（动态）