- 单链表
- 1. 定义
- 2.初始化
- 3.判空
- 4.求表长
- 5.按序号查找
- 6.按值查找
- 8.在第i个位置插入e
- 9.头插
- 10.尾插
- 11.头插建立链表
- 12.尾插建立链表
- 13.删除节点
- 14.打印节点
- 15.销毁节点
- 16.翻转链表
- 17.不遍历链表删除非尾节点
- 18.遍历一次找到中间节点 -
- 19.遍历一遍，找到倒数第k个节点(k从1开始)
- 20.冒泡排序
- 21.插入排序
- 22.快速排序
- 23.合并两个有序链表
- 24.判断链表是否有环，如果有环，求长度和入口
单链表
初始化链表头部指针会用到二级指针或者一级指针的引用
销毁链表会用到二级指针或者一级指针的引用
插入、遍历、删除、清空用一级指针即可
定义成指针用 ->, 未定义为指针用 .
1. 定义
typedef struct Lnode{
int data;
struct Lnode *next;
}Lnode, *LinkList;
2.初始化
int InitList(LinkList *L){
*L = (LinkList)malloc(sizeof(LNode));
if( !(L) ){
print("Init Error");
return False;
}
(*L)->next = NULL;
return True;
}
3.判空
bool Empty(LinkList L){
if(L->next == NULL){
return True;
}else{
return False;
}
}
4.求表长
int Length(LinkList L){
int len = 0;
LNode *p;
p = L->next;
if(L->next == NULL){
return len;
}
while(L->next != NULL){
p = p->next;
len++;
}
return len;
}
5.按序号查找
Lnode *GetElem(LinkList L, int i){
int j = 1;
Lnode *p = L->next;
if(i == 0){
return L;
}
if(i < 1){
return L;
}
while(p->next != NULL && j < i){
p = p->next;
j++;
}
return p;
}
6.按值查找
int LocateElem(LinkList L, int e){
Lnode *p = L->next;
int i = 1;
if(Empty(L)){
printf("Empty! ")；
return false;
}
while(p != NULL && p->data != e){
p = p->next;
i++;
}
return i;
}
8.在第i个位置插入e
LinkList ListInsert(LinkList L, int i, int e){
LNode *p;
LNode *s;
p = GetElem(i);
s = (LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = p->next;
p->next = s;
return L;
}
9.头插
LinkList HeadInset(LinkList L, int e){
LNode *s;
s = (LinkList)malloc(sizeof(LNode));
s->data = e;
s->next = L->next;
L->next = s;
return L;
}
10.尾插
LinkList TailInsert(LinkList L, int e){
LNode *s, *p = L->next;
s = (LinkList)malloc(sizeof(LNode));
s->data = e;
while(*p->next != NULL){
p->next = s;
}
s->next = NULL;
return L;
}
11.头插建立链表
LinkList HeadCreateList(LinkList &L, int a[], int n){
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
LNode *s;
fro(int i = 0; i < n; i++){
s = (LinkList)malloc(sizeof(LNode));
s->data = a[i];
s->next = L->next;
L->next = s;
}
return L;
}
12.尾插建立链表
LinkList TailCreateList(LinkList &L, int a[], int n){
L = (LinkList)malloc(sizeof(LNode));
L->next = NULL;
LNode *s, *p = L;
for(int i = 0; i < n; i++){
s = (LinkList)malloc(sizeof(LNode));
s->data = a[i];
p->next = s;
p = s;
}
s->next = NULL:
return L;
}
13.删除节点
LinkList ListDelet(LinkList L, int i, int *data){
LNode *p, *q;
if(i < 0 && i > Length(L)){
print("error");
return false;
}
p = GetElem(L, i-1);
q = p->next;
data = q->data;
p ->next = q->next;
free(q);
}
14.打印节点
void PrintList(LinkList L){
LNode *p;
p = L->next;
int i = 1;
if(Empty(L)){
print("Empty! ");
}
while(p != NULL){
print("LinkList %d' data is %d", i, p->data);
p = p->next;
i++;
}
}
15.销毁节点
void DestroyList(LinkList &L){
LNode = *p;
while(L){
p = L->next;
free(L);
L = p;
}
}
16.翻转链表
LinkList ReverseList(LinkList L){
LNode *pNext, *pPre = NULL;
if(L == NULL || L->next = L){
return L;
}
while(L != NULL){
pNext = L->next;
L->next = pPre;
pPre = L;
L = pNext;
}
return L;
}
迭代
LinkList ReverseList(LinkList L){
if(L == NULL || L->next == NULL){
return L;
}
LNode *NewHead = ReverseList(L->next);
L->next->next = L;
L->next = NULL;
return NewHead;
}
17.不遍历链表删除非尾节点
void RemoveNodeNotTail(LNode *p){
LNode *pNext = p->next;
p->dat = pNext->data;
p->next = pNext->next;
free(pNext);
}
18.遍历一次找到中间节点
LNode* Findmid(LinkList L){
LNode *pSlow = L;
LNode *pFast = L->next;
assert(L);
while(pFast){
pSlow = pSlow->next;
pFast = pFast->next->next;
}
return pSlow;
}
19.遍历一遍，找到倒数第k个节点(k从1开始)
LNode* FindK(LinkList L){
LNode *pSlow = L;
LNode *pFast = L;
while(k){
pFast = pFast->next;
k--;
}
while(pFast){
pSlow = pSlow->next;
pFast = pFast->next
}
return pSlow;
}
20.冒泡排序
LinkList BubbleSort(LinkList L){
LNode *tail = NULL;
LNode *Count;
if(L == NULL || L->next == NULL){
return;
}
/*排序次数*/
for(Count = L->next; Count != NULL; Count = Count->next){
LNode *p = L->next;
for(; p->next != tail; p = p->next){
if(cmp(p->data, p->next->data)){
swap(&p->data, &p->next->data)
}
}
tail = p;
}
return L;
}
bool cmp(int a, int b){
return(a>b?1:0); //升序
/*
return(a<b?1:0); //降序
*/
}
void swap(int *a, int *b){
int tmp = *a;
*a = *b;
*b = tmp;
}
21.插入排序
LinkList InsertSort(LinkList L){
LNode *p = L->next->next;
L->next->next = NULL;
while(p != NULL){
LNode *p = p->next;
LNode *pre = L;
while(pre->next!=NULL && cmp(pre->next->data,p->data){
pre = pre->next;
}
p->next = pre->next;
pre->next = p;
p = q;
}
return L;
}
22.快速排序
void QuickSort(LNode *left, LNode *right){
if(left =+ right || left->next == NULL){
return;
}
LNode *pivot_index = Partition(left, right);
QuickSort(left, pivot_index);
QuickSort(pivot_index->next, right);
}
LNode* Partition(LNode *left, LNode *right){
LNode *p1 = left;
LNode *p2 = p1->next;
int pivot = left->data;
while(p2 != right){
if (cmp(p2->data, left->data)){
swap(p1->next->data, p2->data)
}
p2 = p2->next;
}
}
bool cmp(int a, int b){
return(a>b?1:0); //升序
/*
return(a<b?1:0); //降序
*/
}
void swap(int *a, int *b){
int tmp = *a;
*a = *b;
*b = tmp;
}
23.合并两个有序链表
LinkList MergeOrderedList(LinkList L1, LinkList L2){
LNode *p = NULL;
while(L1 && L2){
if(p = NULL){
if(L1->next->dat <= L2->next->data){
p = L1;
L1 = L1.next;
}else{
p = L2;
L2 = L2->next;
}
}
if(p != NULL && (L1->data <= L2->data)){
p->next = L1;
L1 = L1->next;
p = p->next;
}
else if(p != NULL && (L1->data > L2->data)){
p->next = L2;
L2 = L2->next;
p = p->next;
}
}
if(L1 == NULL){
p->next = L2;
}
if(L2 == NULL){
p->next = L1;
}
return L;
}
24.判断链表是否有环，如果有环，求长度和入口
//判断是否有环
int LinkListHasCycle(LNode *head){
if(head == NULL){
return head;
}
LNode *pslow = head;
LNode *pfast = head;
while(pfast != NULL && pfast->next->next != NULL){
pslow = pslow->next;
pfast = pfast->next->next;
if(pslow == pfast){
return 1;
}
}
return 0;
}
//返回相遇节点
LNode* LinkListHasCycle1(LNode *head){
if(head == NULL){
return head;
}
LNode *pslow = head;
LNode *pfast = head;
while(pfast != NULL && pfast->next->next != NULL){
pslow = pslow->next;
pfast = pfast->next->next;
if(pslow == pfast){
return pslow;
}
}
return NULL;
}
//求环的长度
int LinkListGetCycleLen(LNode *head){
if(head == NULL){
return NULL;
}
LNode *pmeet = LinkListHasCycle1(head);
if(pmeet == NULL){
return 0;
}
LNode *p = pmeet->next;
int len = 1;
while(p != pmeet){
p = p->next;
++len;
}
return Len;
}
//环的入口,首元素节点到入口的长度等于相遇点到入口点的长度。
LNode* LinkListGetCycleEnter(LNode *head){
if(head == NUll){
return NULL;
}
LNode *p1 = head;
LNode *p2 = LinkListHasCycle1(head);
while(p1 != p2){
p1 = p1->next;
p2 = p2->next;
}
return p1;
}
到此这篇对于一个头指针为head的单向链表（在一个头指针为head的单向链表中）的文章就介绍到这了,更多相关内容请继续浏览下面的相关 推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/qkl-jc/14030.html