1、顺序表新增：在第i个位置插入元素e

静态顺序表：

// 408_sxb.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
using namespace std;
#define eletype char
#define maxsize 50

typedef struct SList{
    eletype A[maxsize];
    unsigned lenth = 0;  //长度为定义无符号数
}SList,*SSList;

void initList(SSList L) {
    if (!L->A) {
        exit(OVERFLOW);
    }
    for (int i = 0; i < 10; i++)
    {
        L->A[i] = i+97;
        L->lenth++;
    }
}

void printSList(SSList L) {
    cout << "静态表:";
    for (int i = 0; i < L->lenth; i++) {
        cout << L->A[i]<<" ";
    }
    cout << endl;
}

void AddSList(SSList L,eletype e,int n) {
    for (int i = L->lenth-1; i >=n-1; i--) {
        L->A[i + 1] = L->A[i];
    }
    L->A[n-1] = e;
    L->lenth++;
}

int main()
{
    SSList L = new SList;
    initList(L);
    printSList(L);
    AddSList(L, 'z', 4);
    printSList(L);
    return 0;
}

动态顺序表：
**note：**动态顺序表的结点中的元素一开始没开辟其余的空间还需要自己定义；如不定义就会出现如下错误：

为了使其得要空间，我们可以使用该语句：L->D = (eletype*)malloc(maxsize * sizeof(eletype));
对于动态链表我们还可以重新为其分配空间语句为:
:eletype* p; p = (eletype*)realloc(L->D, (maxsize + addsize)*sizeof(eletype));

// 408_sxb.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
using namespace std;
#define eletype char
#define maxsize 50
#define addsize 50

typedef struct DList {
    eletype* D;
    unsigned length=0;
}DList,*DDList;

void InitDList(DDList L) {
    if (!L->D)
    {
        exit(OVERFLOW);
    }

    if (L->length == maxsize) {
        eletype* p;
        p = (eletype*)realloc(L->D, (maxsize + addsize)*sizeof(eletype));
    }

    for (int i = 0; i < 10; i++) {
        //*(L->D + i) = i + 97;
        L->D[i] = i + 97;
        L->length++;
    }
}

void printDList(DDList L) {
    cout << "动态表：";
    for (int i = 0; i < L->length; i++) {
        cout << *(L->D+i)<<" ";
    }
    cout << endl;
}

void AddDList(DDList L,int n,eletype e) {
    for (int i = L->length; i >= n - 1; i--) {
        *(L->D + i + 1) = *(L->D + i);
    }
    L->D[n - 1] = e;
    L->length++;
}

int main()
{
    DDList L = new DList;
    L->D = (eletype*)malloc(maxsize * sizeof(eletype));
    InitDList(L);
    printDList(L);
    AddDList(L,5,'z');
    printDList(L);

    return 0;
}

在长度为n的（）上，删除第一个元素，其算法的时间复杂度为O(n)
A.只有表头指针的不带表头结点的循环单链表
B.只有表尾指针的不带表头结点的循环单链表
C.只有表尾指针的带表头结点的循环单链表
D.只有表头指针的带表头结点的循环单链表

答案：A

分析：
单链表只能按单方向顺序访问节点，按题目意思，只有当A条件时，并当新元素的节点从表头插入，使得第一个元素的节点在表尾，才成立。这样表头指针顺序访问节点，访问至链表尾部时，复杂度刚好为O(n)。

对于B而言，不带头节点循环链表，表尾指针，如果是头插法则第一元素就是表尾指针rear（假设表尾指针为rear）所指的节点，即当前节点，时间复杂度为O(1)。如果是正常顺序插入节点（即非头插法），由于是循环链表，表尾指针rear指向最后一个元素，rear->next即为第一个元素（因为循环链表，表尾的next是表头，且没有头节点），时间复杂度仍然是O(1)，所以B不成立。
对于C而言，和B情况相似，多了一个表头节点，如果是头插法，则和B一样表尾指针rear所指当前元素即为第一个元素，时间复杂度为O(1)。如果是正常顺序插入节点，则比B多一个头节点，就变成rear->next->next，但时间复杂度仍然是O(1)，所以C不成立。
对于D而言，比A多一个头节点，虽然当头插法时时间复杂度为O(n+1)，根据次数化解原则，就为O(n)，但是答案不是选D（我也不是很清楚，老师讲解时直接跳过没有解释清楚，希望大佬评论解答，感激！！！）

题目要求：

对长度为n的顺序表L，编写一个时间复杂度为O（n），空间复杂度为O（1）的算法
该算法删除线性表中所有值为x的数据元素

/*对长度为n的顺序表L，编写一个时间复杂度为O（n），空间复杂度为O（1）的算法
该算法删除线性表中所有值为x的数据元素*/
#include <iostream>
#include <cstring>
#include<math.h>
#define MAXSIZE 20
#define ElemType int//不加分号
using namespace std;
typedef struct {
	ElemType data[MAXSIZE];
	int length;
}SqList;
bool InitList(SqList &L) {
	memset(L.data, 0, sizeof(L));
	if (!L.data)
		exit(0);
	L.length = 0;
	return true;
}
void CreateList(SqList &L, int n) {
	for (int i = 0;i<n;i++) {
		cin >> L.data[i];
		L.length++;
	}
}
bool DeleteX(SqList &L,ElemType e) {//推荐做法，更容易想
	//注释部分的做法没有达到空间复杂度为o（1），也不会满足时间复杂度要求
	/*int x[MAXSIZE];
	int j=-1;
	memset(x, 0, sizeof(x));*/
	int k=0;//用k来记录所有值不是x的元素的下标，边扫描边统计k，并将不等于x的元素向前移动k个位置，最后修改L的长度
	for (int i = 0;i <L.length;i++) {
		if (L.data[i] != e) {
			/*j++;
			x[j] = i;*/
			L.data[k] = L.data[i];
			k++;
		}
		
	} 
	L.length = k;
	return true;
}
void DeleteX2(SqList &L, ElemType e) {
	int k = 0, i = 0;//用k来记录等于x的元素的个数，边扫描L边统计k，并将不等于x的元素前移k个位置，最后修改L的长度
	while (i<L.length)
	{
		if (L.data[i] == e)
			k++;//用k来记录等于x的元素的个数，边扫描L边统计k
		else
			L.data[i - k] = L.data[i];//将不等于x的元素前移k个位置
		i++;
	}
	L.length -= k;//修改L的长度
}
void PrintList(SqList L) {
	cout << "表中元素分别为";
	for (int i = 0;i<L.length;i++)
		cout << L.data[i] << "  ";
	cout << endl;
}
int main() {
	SqList L;
	InitList(L);
	int n = 0;
	cout << "请输入要创建的表的长度：" << endl;
	cin >> n;
	cout << "请依次输入各个元素：（用空格隔开）" << endl;
	CreateList(L, n);
	cout << "请输入想要删除元素的值（即x的值）：" << endl;
	ElemType e;
	cin >> e;	
	DeleteX2(L,e);
	PrintList(L);
	return 0;
}