数据结构--顺序表、单链表

线性表是指顺序表和单链表

//顺序表数据结构
typedef struct
{
ElemType data[MaxSize];//顺序表元素
int length; //顺序表当前长度
}SqList;

//单链表结点数据结构
typedef struct LNode
{
ElemType data;//数据域
struct LNode *next;//指针域
}LNode,*LinkList;

顺序表

#define MaxSize 100
typedef struct  { int data [MaxSize]; int length; }SqList;//***********************************   基本操作函数  *******************************************int InitList(SqList &L)
{memset(L.data, 0, sizeof(L));L.length = 0;return 0;}
bool CreateList(SqList& L, int n)
{if (n<0 || n>MaxSize)false;for (int i = 0; i < n; i++){scanf("%d", &L.data[i]);L.length++;}return true;
}bool InsertList(SqList& L, int i, int e)
{if (i<1 || i>L.length + 1) //判断位置是否有效{printf("位置无效！！！\n");return false;}if (L.length >= MaxSize)//判断存储空间是否已满{printf("当前存储空间已满！！！\n");return false;}for (int j = L.length; j >= i; j--){L.data[j] = L.data[j - 1]; // 第i个元素开始后移}L.data[i - 1] = e;L.length++;return true;
}bool  ListDelete(SqList& L, int i)
{if (i<1 || i>L.length){printf("位置无效！！！\n");return false;}for (int j = i; j <= L.length - 1; j++)//位置i之后元素依次前移覆盖{L.data[j - 1] = L.data[j];}L.length--;return true;
}//查找函数 按位置从小到大查找第一个值等于e的元素 并返回位置
int LocateElem(SqList L, int e)
{for (int i = 0; i < L.length; i++)//从低位置查找{if (L.data[i] == e)return i + 1;}return 0;
}void Reverse(SqList& L)
{if (L.length)for (int i = 0; i < L.length - 1 - i; i++){int t = L.data[i];L.data[i] = L.data[L.length - 1 - i];L.data[L.length - 1 - i] = t;}
}//清空顺序表
void ClearList(SqList& L) {L.length = 0;
}//奇偶分开并排序
void SplitSort(SqList& L)
{int Even = 0;int Odd = L.length - 1;int i = 0;int j = L.length - 1;bool flag = false; // 交换标志if (L.length)for (; i < j; i++, j--){while (L.data[i] % 2 != 0 && i < L.length - 1)i++;while (L.data[j] % 2 == 0 && j > 0)j--;if (L.data[i] % 2 == 0 && L.data[j] % 2 != 0 && i < j){int temp = L.data[i];L.data[i] = L.data[j];L.data[j] = temp;flag = true;}if (!flag) //没有交换{if (i > j) { // 恰好奇偶分开Even = j;Odd = i;}else {Even = L.length - 1;//全奇数Odd = 0; //全偶数}}}if (flag)//有交换{for (int i = 0; i < L.length; i++)if (L.data[i] % 2 == 0){Odd = i;Even = i - 1;break;}}sort(L.data, L.data + Even + 1);	// include<list>sort(L.data + Odd, L.data + L.length);
}//********************************功能实现函数**************************************//void PrintList(SqList L)
{printf("当前顺序表所有元素:");for (int i = 0; i < L.length; i++){printf("%d ", L.data[i]);}printf("\n");
}void Create(SqList& L)
{int n; bool flag;L.length = 0;printf("请输入要创建的顺序表长度(>1):");scanf("%d", &n);printf("请输入%d个数（空格隔开）:", n);flag = CreateList(L, n);if (flag) {printf("创建成功！\n");PrintList(L);}else printf("输入长度非法！\n");}void Insert(SqList& L)
{int place; int e; bool flag;printf("请输入要插入的位置(从1开始)及元素:\n");scanf("%d%d", &place, &e);flag = InsertList(L, place, e);if (flag){printf("插入成功！！！\n");PrintList(L);}
}void Delete(SqList& L)
{int place; bool flag;printf("请输入要删除的位置(从1开始):\n");scanf("%d", &place);flag = ListDelete(L, place);if (flag){printf("删除成功！！！\n");PrintList(L);}
}void Search(SqList L)
{int e; int flag;printf("请输入要查找的值:\n");scanf("%d", &e);flag = LocateElem(L, e);if (flag){printf("该元素位置为:%d\n", flag);}elseprintf("未找到该元素！\n");
}void menu() {printf("********1.创建                        2.插入*********\n");printf("********3.删除                        4.查找*********\n");printf("********5.倒置                        6.分奇偶排序***\n");printf("********7.输出                        8.清空*********\n");printf("********9.退出                              *********\n");
}int main() {SqList L;int choice = 0;;InitList(L);//switch (choice)//{//case 1:Create(L); break;//case 2:Insert(L); break;//case 3:Delete(L); break;//case 4:Search(L); break;//case 5:Reverse(L); break;//case 6:SplitSort(L); break;//case 7:PrintList(L); break;//case 8:ClearList(L); break;//default:printf("输入错误！！！\n");//}while (1){menu();printf("请输入菜单序号：\n");scanf("%d", &choice);if (9 == choice) break;switch (choice){case 1:Create(L); break;case 2:Insert(L); break;case 3:Delete(L); break;case 4:Search(L); break;case 5:Reverse(L); break;case 6:SplitSort(L); break;case 7:PrintList(L); break;case 8:ClearList(L); break;default:printf("输入错误！！！\n");}system("pause");system("cls");}return 0;
}

单链表

#define MaxSize 100
typedef struct  LNode{ int data; struct LNode *next; }LNode,*LinkList;//***********************************   基本操作函数  *******************************************int InitList(LinkList &L)
{L = new LNode;L->next = NULL;return 0;}
//获取单链表长度 头结点无数据，不算
int ListLength(LinkList L)
{LinkList p = L; int sum = 0;while (p){sum++;p = p->next;}return sum - 1;//去除头结点
}//插入函数--后插法 插入到第i(1<=i<=length+1)个位置 即i-1之后 不必区分i的位置
bool ListInsert(LinkList& L, int i, int e)
{LNode* s; LinkList p = L; int j = 0;while (p && (j < i - 1))//j指到i-1位置或者p已经到最后时跳出{p = p->next;++j;}if (!p || j > i - 1)//i<1或者i>ListLength(L)+1时,插入位置无效 不调用ListLength,提高效率{printf("插入位置无效！！！\n");return false;}s = new LNode;s->data = e;s->next = p->next;p->next = s;return true;
}bool ListDelete(LinkList& L, int i)
{LNode* s; LinkList p = L; int j = 0;LinkList q;while (p && (j < i - 1))//j指到i-1位置{p = p->next;++j;}if (p == nullptr || !(p->next) || j > i - 1)//i<1或者i>ListLength(L)时,删除位置无效{printf("删除位置无效！！！\n");return false;}q = p->next;p->next = q->next;free(q);//释放空间return true;
}LNode* LocateElem(LinkList L, int e)
{LNode* p = L;while (p && (p->data != e)){p = p->next;}return p;
}//********************************功能实现函数**************************************////遍历输出函数
void PrintList(LinkList L)
{LinkList p = L->next;	//跳过头结点if (ListLength(L)){printf("当前单链表所有元素:");while (p){printf("%d ", p->data);p = p->next;}printf("\n");}else{printf("当前单链表已空！\n");}
}void Insert(LinkList& L)
{int place; int e; bool flag;printf("请输入要插入的位置(从1开始)及元素:\n");scanf("%d%d", &place, &e);flag = ListInsert(L, place, e);if (flag){printf("插入成功！！！\n");PrintList(L);}
}void Delete(LinkList L)
{int place; bool flag;printf("请输入要删除的位置(从1开始):\n");scanf("%d", &place);flag = ListDelete(L, place);if (flag){printf("删除成功！！！\n");PrintList(L);}
}void Search(LinkList L)
{int e; LNode* q;printf("请输入要查找的值:\n");scanf("%d", &e);q = LocateElem(L, e);if (q){printf("找到该元素！\n");}elseprintf("未找到该元素！\n");
}void menu() {printf("********1.后插    2.删除*********\n");printf("********3.查找    4.输出*********\n");printf("********5.退出          *********\n");
}int main() {LinkList L;int choice = 0;;InitList(L);while (1){menu();printf("请输入菜单序号：\n");scanf("%d", &choice);if (9 == choice) break;switch (choice){case 1:Insert(L); break;case 2:Delete(L); break;case 3:Search(L); break;case 4:PrintList(L); break;default:printf("输入错误！！！\n");}system("pause");system("cls");}return 0;
}