数据结构---顺序表

?1.线性表的定义和特点

?

?

?

?

顺序储存结构：数组? ? ? ? 链式储存结构：指针

?

?2.线性表的类型定义

3.顺序存储结构

?

?

?

等同于

struct Polynomial{
    float p;
    int   e;
}

typeof struct{
    struct Polymomial*elem;
    int length;
}Sqlist;

关于数组的动态和静态分配：

?

4.顺序表基本操作的实现

示意图：

?补充：操作算法中用到的预定义常量和类型

?一.初始化

注意这里 （SqList &?L） &表示引用参数，函数内部的改变跳出函数后仍然有效。

补充：关于c语言和c++中的内存动态分配

C：

C++:

?二.销毁、清空顺序表、求顺序表L的长度、判断顺序表是否为空

三、顺序表的创建

不要忘记将n的值赋给sq->n!

四、顺序表的取值

五、顺序表的查找

算法复杂度分析：?

最好情况：元素在第一个位置，比较一次查找成功，时间复杂度：O(1).

最坏情况：元素在最后一个位置，比较n次查找成功，时间复杂度：O(n).

平均情况：第一个元素需要比较1次，第二个元素需要比较2次，第n个元素需要比较n次，累加。

? ?

平均时间复杂度：O（n).

六、顺序表的插入

注意这里循环是从后往前， 先后移要插入位置后面的元素，再插入，表长加一。

算法复杂度分析：?

平均时间复杂度：O（n).

?

七、顺序表的删除

**注意判断i位置是否合法的条件，在插入里是，i<1||i>L.length+1;? 删除则是i<1||i>L.length.

算法复杂度分析：?

平均时间复杂度：O（n).

**注意为什么插入和删除时元素移动的循环条件一个是从后往前一个是从前往后。

**注意插入和删除计算平均复杂度的不同：

八、将元素插入到一有序顺序表中

PTA? 有序数组的插入

裁判测试程序样例：

#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 10
typedef enum {false, true} bool;
typedef int ElementType;

typedef int Position;
typedef struct LNode *List;
struct LNode {
    ElementType Data[MAXSIZE];
    Position Last; /* 保存线性表中最后一个元素的位置 */
};

List ReadInput(); /* 裁判实现，细节不表。元素从下标0开始存储 */
void PrintList( List L ); /* 裁判实现，细节不表 */
bool Insert( List L, ElementType X );

int main()
{
    List L;
    ElementType X;

    L = ReadInput();
    scanf("%d", &X);
    if ( Insert( L, X ) == false )
        printf("Insertion failed.\n");
    PrintList( L );

    return 0;
}

/* 你的代码将被嵌在这里 */

注意，这里定义里的Last相当于数组中元素的下标，而不是表长。

bool Insert( List L, ElementType X )
{
    if(L->last==MAXSIZE-1){
        return false;
    }
    for(int i=0;i<=L->Last;i++){
        if(X==L.Data[i]){
            return false;
        }
    }
    
    int i=L->last;
    while(i>=0 && X>L->Data[i]){
        L->Data[i+1]=L->Data[i];
        i--;
    }
    L->Data[i+1]=X;
    L->Last++;
    return true;
  
}

**完整代码：

#include <stdio.h>
#define MaxSize 105
typedef int ElemType;
//用ElemType作为元素类型别名可以提高代码的可读性和可维护性
//可维护性：如果想将线性表里的元素改成double类型 
//只需要将这条语句改成  typedef double ElemType;

typedef struct {
	ElemType  a[MaxSize];//顺序表的元素
	int n;//顺序表的长度
}SeqList;

//输出系统菜单
void printMenu();

//0.输出顺序表sq
void print(SeqList sq);

//1.创建顺序表（用指针实现）
void create(SeqList *sq);

//2.查找一个元素item在顺序表的位置；找不到返回-1?
int findPos(SeqList sq, ElemType item);

//3.在顺序表的第i个位置插入一个元素item，插入成功返回1；失败返回-1??
int insert(SeqList *sq, int i, ElemType item);

//4.删除顺序表第i个位置的元素??
int del(SeqList* sq, int i, ElemType item);


//5.修改顺序表第i个位置的元素??
int modify(SeqList * sq, int i, ElemType item);

//6.对顺序表sq排序???
void sort(SeqList * sq);


//7.在有序的顺序表中插入一个元素item??
void insertSorted(SeqList  * sq, ElemType item);




//8.合并2个有序表s1和s2到新表sq???
void mergeSorted(SeqList  * sq, SeqList s1, SeqList s2);



int main()
{
	//打印主菜单
	printMenu();
	int choice, p, x;//用户选择、位置、插入
	SeqList sq;//创建线性表
	sq.n = 0;//初始长度为0

	//进入菜单循环
	while (~scanf("%d", &choice)) {
		switch (choice) {
			//case里有多条语句时 要加上大括号
		case 0:printf("0.输出顺序表\n");
			print(sq);
			break;

		case 1:printf("1.创建顺序表\n");
			create(&sq);
			printf("创建成功，输出顺序表\n");
			print(sq);
			break;


		case 2:
		{
			printf("2.查找一个元素item在顺序表的的位置\n");
			scanf("%d", &x);
			int pos = findPos(sq, x);//避免重复调用函数
			if (pos == -1) {
				printf("查找失败");
			}
			else {
				printf("查找成功，元素位于%d", pos);
			}
			break;
		}

		case 3:
		{printf("3.在顺序表第i个位置插入一个元素item\n");
		printf("请输入插入的位置和元素：");
		int p;
		ElemType x;
		scanf("%d%d", &p, &x);
		if (insert(&sq, p, x) == -1) {
			printf("插入失败!\n");
		}
		else {
			print(sq);
		}
		break;
		}

		case 4:
		{printf("4.删除顺序表第i个位置的元素\n");
		int i;
		ElemType x;
		printf("请输入删除的位置和元素");
		scanf("%d %d", &i, &x);
		int dell = del(&sq, i, x);
		if (dell == -1) {
			printf("删除失败!\n");
		}
		else {
			printf("删除成功\n");
			print(sq);
		}
		break;
		}

		case 5: { printf("5.修改顺序表第i个位置的元素\n");


			printf("请输入要修改的位置和元素");
			int p;
			ElemType x;
			scanf("%d%d", &p, &x);
			int mod = modify(&sq, p, x);
			if (mod == -1) {
				printf("修改失败!\n");
			}
			else {
				printf("修改成功\n");
				print(sq);
			}
			break;
		}
		case 6:printf("6.对顺序表sq排序\n");
			printf("排序后的顺序表为：");
			sort(&sq);
			print(sq);
			break;

		case 7: {printf("7.在有序的顺序表中插入一个元素item\n");

			printf("请输入要插入的元素：");
			scanf("%d", &x);
			insertSorted(&sq, x);
			print(sq);
			break;
		}

		case 8: {printf("8.合并有序表\n");
			SeqList s1, s2;
			printf("请输入2个有序表（务必从小到大排序）：\n");
			create(&s1);
			create(&s2);
			mergeSorted(&sq, s1, s2);
			print(sq);
			break;
		}
		case 19:printMenu();
			return 0;


		case 20:printf("系统即将退出，欢迎再次使用！\n");
			break;


		}
		}
	}




	//输出系统菜单
	void printMenu()
	{
		printf("欢迎进入顺序表操作子系统!\n");
		printf("--------------------------------------------\n");
		printf("0.输出顺序表\n");
		printf("1.创建顺序表\n");
		printf("2.查找一个元素item在顺序表的位置\n");
		printf("3.在顺序表第i个位置插入一个元素item\n");
		printf("4.删除顺序表第i个位置的元素\n");
		printf("5.修改顺序表第i个位置的元素\n");
		printf("*******************************************\n");
		printf("6.对顺序表sq排序\n");
		printf("7.在有序的顺序表中插入一个元素item\n");
		printf("8.合并有序表\n");
		printf("*******************************************\n");
		printf("9.预留功能\n");
		printf("*******************************************\n");
		printf("19.输出系统菜单\n");
		printf("20.退出系统\n");
		printf("--------------------------------------------\n");

	}

	//0.输出顺序表
	void print(SeqList sq)
	{
		printf("顺序表的长度是%d\n", sq.n);
		for (int i = 0; i < sq.n; i++) {
			printf("%d ", sq.a[i]);
		}
		printf("\n");
	}

	//1.创建顺序表
	void create(SeqList * sq)
	{
		printf("请输入顺序表的元素（ctrl+z结束输入）：\n");
		int n = 0, x;//n这里是顺序表元素的个数
		while (~scanf("%d", &x)) {
			sq->a[n] = x;
			n++;
		}
		sq->n = n;
	}

	//2.查找一个元素item在顺序表的位置；找不到返回-1??
	int findPos(SeqList sq, ElemType item)
	{
		for (int i = 0; i < sq.n; i++) {
			if (sq.a[i] == item) {
				return i + 1;//查找成功 返回在表中位置
			}
		}
		return -1;//查找失败，返回信息-1
	}



	//3.在顺序表的第i个位置插入一个新元素item，插入成功返回1；失败返回-1
	int insert(SeqList * sq, int i, ElemType item)
	{
		 if (sq->n >= MaxSize || i < 1 || i > sq->n + 1){
			 //可以在线性表末尾插入元素 即在i = sq->n+1处进行插入
			
			//顺序表长度为n
			//储存空间已满或i的范围不在顺序表范围内时
			return -1;
		}
		for (int j = sq->n - 1; j >= i-1; j--) {
			//从顺序表的最后一个元素开始逐步向前遍历
			sq->a[j+1] = sq->a[j ];
		}
		sq->a[i - 1] = item;//插入元素
		(sq->n)++;
		return 1;
	}


	//4.删除顺序表第i个位置的元素??
	int del(SeqList * sq, int i, ElemType item)
	{
		if (i < 1 || i>sq->n) {
			//i的范围不在顺序表范围内时
			return -1;
		}
		item = sq->a[i - 1];
		for (int j = i; j <= sq->n - 1; j++)
		{
			sq->a[j - 1] = sq->a[j];
		}

		(sq->n)--;
		return 1;
	}

	//5.修改顺序表第i个位置的元素??
	int modify(SeqList * sq, int i, ElemType item)
	{
		if (i<1 || i>sq->n)
		{
			return -1;
		}

		sq->a[i - 1] = item;
		return 1;
	}

	//6.对顺序表sq排序???
	void sort(SeqList * sq)
	{
		for (int i = 0; i < sq->n - 1; i++) {
			for (int j = 0; j < sq->n - i - 1; j++) {
				if (sq->a[j] > sq->a[j + 1]) {
					int t = sq->a[j];
					sq->a[j] = sq->a[j + 1];
					sq->a[j + 1] = t;
				}
			}
		}
	}

	//7.在有序的顺序表中插入一个元素item??
	void insertSorted(SeqList * sq, ElemType item) {


		int i = sq->n - 1;//i初始为倒数第二个元素
		while (i >= 0 && item < sq->a[i]) {//逆向比较

			sq->a[i + 1] = sq->a[i];
			i--;
		}
		sq->a[i+1] = item;
		(sq->n)++;
	}

	//8.合并2个有序表s1和s2到新表sq???
	
void mergeSorted(SeqList* sq, SeqList s1, SeqList s2) {
	int i = 0;  // s1 的索引
	int j = 0;  // s2 的索引

	while (i < s1.n && j < s2.n) {
		if (s1.a[i] <= s2.a[j]) {
			sq->a[sq->n] = s1.a[i];
			i++;
		}
		else {
			sq->a[sq->n] = s2.a[j];
			j++;
		}
		sq->n++;  // sq 的长度加1
	}

	

		// 将 s1 或 s2 剩余的元素插入到 sq 中
		while (i < s1.n) {
			sq->a[sq->n] = s1.a[i];
			i++;
			sq->n++;
		}

		while (j < s2.n) {
			sq->a[sq->n] = s2.a[j];
			j++;
			sq->n++;
		}
	}