LinkList.h
typedef int ElemType;
typedef int Status;typedef struct LNode {ElemType data;struct LNode * next;}LNode,*LinkList;//当第i个元素存在 把值 通过e返回
Status GetElem_L(LinkList, int, ElemType *);//元素插入 2.8
Status ListInsert_L(LinkList,int ,ElemType);//元素删除 2.9
Status ListDelete_L(LinkList ,int ,ElemType * );//创建 2.10
void CreateList_L(LinkList * ,int );// 排序 归并
LinkList SortInList(LinkList L, LinkList H);//2.11 参照排序的归并部分
LinkList.c
#include <stdlib.h>
#include<stdio.h>
#include "./LinkList.h"//当第i个元素存在 把值 通过e返回
Status GetElem_L(LinkList L, int i, ElemType* e) {LinkList p;int j; p = L;p = p->next;//p指向第一个结点j = 0; //计数//寻找第 i个位置结点while (p && j < i){//p指向下一个 结点 j++;p = p->next;++j;};//第i个元素 不存在if (!p || j > i) {return -1;};//返回第i个 结点的值*e = p->data;return 0;};//元素插入
Status ListInsert_L(LinkList L, int i , ElemType e) {LinkList p;LinkList s;int j;p = L;j = -1; //表示头结点位置 0表示第一个结点位置//寻找第i-1个结点while (p && j < i - 1){p = p->next;++j;};if (!p || j > i - 1) {return -1;};//生成新节点s = (LinkList)malloc(sizeof(LNode));s->data = e;//插入s->next = p->next;p->next = s;return 0;
};//元素删除
Status ListDelete_L(LinkList L, int i, ElemType* e) {LinkList p;LinkList q;int j;p = L;j = -1; //表示头结点位置 0表示第一个结点位置//寻找要删除结点的前一个结点while (p->next && j < i - 1){p = p->next;++j;};if (!(p->next) || j > i - 1) {return -1;};//删除q = p->next;//记录一下要删除 结点位置 一会 释放 //p的next指向q的下一个结点 p->next = q->next;*e = q->data; //将删除的结点数据返回//释放free(q);return 0;
};//创建
void CreateList_L(LinkList * L, int n) {LinkList p;int i;//创建一个头结点 并返回给外部使用 *L = (LinkList)malloc(sizeof(LNode));(*L)->next = NULL;for (i = n - 1; i >= 0; --i) {//生成新结点p = (LinkList)malloc(sizeof(LNode));//输入 元素值 scanf_s("%d", &(p->data));//插入 到头结点后面 -》因为每次 新 值 都是插入头结点后面 所以最后插入的在第一个位置p->next = (*L)->next; //当前结点的next指向原先结点(*L)->next = p; //头结点指向当前结点};
};// 排序 归并 L不能传入头结点 需要传入L->next
LinkList SortInList(LinkList L, LinkList H) {LinkList res = H;//递归结束条件if (!L || !(L->next)) {return L;}//计算中点 用来分链表LinkList slow, fast, newList,leftNode,rightNode;//快慢指针找中点slow = L;fast = L->next;while (fast && fast->next) //记录: fast && fast->next 这两个判断顺序 不能写反 如果先 判断fast->next,当fast为空时,fast->next理所当然会出现 nullprt异常{slow = slow->next;fast = fast->next->next;}//分割成两个链表newList = slow->next; //1.新链表slow->next = NULL; //2. 新链表结尾为null//递归分割leftNode = SortInList(L,res);rightNode = SortInList(newList,res);//归并while (leftNode && rightNode){if (leftNode->data <= rightNode->data) {H->next = leftNode;leftNode = leftNode->next;}else {H->next = rightNode;rightNode = rightNode->next;};H = H->next;};if (!leftNode) {H->next = rightNode;}if (!rightNode) {H->next = leftNode;}return res->next;};
Main.c
#include <stdlib.h>
#include<stdio.h>
#include "./LinkList.h"int main() {LinkList l;LinkList p;
/* CreateList_L(&l, 3);ElemType e;GetElem_L(l, 0,&e);printf("%d\n", e);GetElem_L(l, 1, &e);printf("%d\n", e);GetElem_L(l, 2, &e);printf("%d\n", e);*/CreateList_L(&l, 0);printf("插入-------------------------------\n");ListInsert_L(l, 0, 1);ListInsert_L(l, 1, 3);ListInsert_L(l, 2, 2);ListInsert_L(l, 3, 4);ListInsert_L(l, 3, 8);ListInsert_L(l, 3, 9);ListInsert_L(l, 3, 6);p = l;while (p->next){p = p->next;printf("%d\n", p->data);}printf("删除-------------------------------\n");ElemType r;ListDelete_L(l, 3, &r);printf("删除了:%d\n",r);p = l;while (p->next){p = p->next;printf("%d\n", p->data);}printf("sort-------------------------------\n");SortInList(l->next, l);p = l;while (p->next){p = p->next;printf("%d\n", p->data);}printf("end-------------------------------");return 0;
}