线性表单链表算法分析（C语言）

ゝ一纸荒年。 2023-07-13 13:51 9阅读 0赞

#include "pch.h"
    #include <stdio.h>
    #include <stdlib.h>
    
    #define TRUE 1
    #define FALSE 0
    #define OK 1
    #define ERROR 0
    #define OVERFLOW -2
    
    typedef int ElemType;
    typedef int Status;
    
    /*存储结构*/
    typedef struct LNode 
    { 
    	ElemType data;
    	struct LNode *next;
    }LNode,*LinkList;
    
    /*头插法建表*/
    void CreateListF(LinkList *L,ElemType a[],int n) 
    { 
    	LinkList s;
    	int i;
    	*L = (LinkList)malloc(sizeof(LNode));
    	(*L)->next = NULL;
    	for (int i = 0; i < n;i++) { 
    		s = (LinkList)malloc(sizeof(LNode));
    		s->data = a[i];
    		s->next = (*L)->next;         //将s插入开始节点之前，头结点之后
    		(*L)->next = s;
    	}
    }
    
    /*尾插法建表*/
    void CreateListR(LinkList *L,ElemType a[],int n) 
    { 
    	LinkList s, r;
    	int i;
    	(*L) = (LinkList)malloc(sizeof(LNode));//创建头结点
    	r = (*L);                             //r开始时指向头节点
    	for (i = 0; i < n;i++) {              //循环建立数据节点
    		s = (LinkList)malloc(sizeof(LNode));  //创建数据节点s
    		s->data = a[i];                   //将s插入r之后
    		r->next = s;
    		r = s;
    	}
    	r->next = NULL;                      //为节点next域置为NULL
    }
    
    /*删除单链表元素最大的节点，假设节点唯一*/
    void delmaxnode(LinkList *L) 
    { 
    	LinkList p = (*L)->next, pre = (*L), maxp = p, maxpre = pre;
    	while (p) { 
    		if (maxp->data<p->data) {        //若找到一个更大的节点
    			maxp = p;
    			maxpre = pre;
    		}
    		pre = p;                        //p,pre同步后移一个节点
    		p = p->next;
    	}
    	maxpre->next = maxp->next;
    	free(maxp);
    }
    
    /*使元素递增有序排列*/
    void sort(LinkList *L) 
    { 
    	LinkList p, pre, q;
    	p = (*L)->next->next;//p指向第二个节点
    	(*L)->next->next = NULL;//构造只含有一个节点的链表（一个节点是有序的）
    	while (p) { 
    		q = p->next;//q指向p的后继节点
    		pre = *L;
    		while (pre->next&&pre->next->data<p->data) { 
    			pre = pre->next;
    		}
    		p->next = pre->next;
    		pre->next = p;
    		p = q;
    	}
    }
    
    /*所有节点逆置*/
    void Rerverse(LinkList *L) 
    { 
    	LinkList p = (*L)->next, q;
    	(*L)->next = NULL;
    	while (p) { 
    		q = p->next;
    		p->next = (*L)->next;
    		(*L)->next = p;
    		p = q;
    	}
    }
    
    /*分解split，L1尾插法，L2头插法*/
    void split(LinkList *L,LinkList *L1,LinkList *L2) 
    { 
    	LinkList p = (*L)->next, q, r1;
    	*L1 = *L;
    	r1 = *L1;
    	*L2 = (LinkList)malloc(sizeof(LNode));
    	(*L2)->next = NULL;
    	while (p) { 
    		r1->next = p;
    		r1 = p;
    		p = p->next;
    		q = p->next;;
    		p->next = (*L2)->next;
    		(*L2)->next = p;
    		p = q;
    	}
    
    }
    
    void visit(ElemType e) 
    { 
    	printf("%d",e);
    }
    
    void TraverseList(LinkList L,void (*visit)(ElemType)) 
    { 
    	LinkList p = L->next;
    	while (p) { 
    		visit(p->data);
    		p = p->next;
    	}
    }
    
    int main() 
    { 
    	LinkList L,R;
    	ElemType a[] = { 1,2,3,4,5};
    	CreateListF(&L,a,5);
    	CreateListR(&R,a,5);
    	TraverseList(L, visit);
    	printf("\n");
    	delmaxnode(&L);
    	TraverseList(L, visit);
    	printf("\n");
    	TraverseList(R,visit);
    
    }