C语言线性单链表相关函数和算法的基本实现详细教程
程序员文章站
2022-05-17 23:48:06
备考期间尝试写了一些基本数据结构的c语言实现,现做以下记录(基本数据元以int型为例):
全局定义及依赖:
#include
#include
#define ok 1
#defi...
备考期间尝试写了一些基本数据结构的c语言实现,现做以下记录(基本数据元以int型为例):
全局定义及依赖:
#include #include #define ok 1 #define error 0 #define end null
链表结点定义:
typedef struct lnode { int data; struct lnode *next; }node,*linkedlist;
链表初始化:
//初始化链表 linkedlist initlist() { node *l; l = (node *)malloc(sizeof(node)); if(l==null) { printf("init error!"); } l->next = null; printf("init ok!\n"); return l; }
头插法生成链表 即在头结点后插入新元素 :
//头插法生成链表 即在头结点后插入新元素 linkedlist createlisth(int n) { int i = 0; node *l; l = (node *)malloc(sizeof(node)); l->next = null; int x; while(idata = x; p->next = l->next; l->next = p; i++; } return l; }
尾插法生成链表 即在尾结点后插入新元素:
//尾插法生成链表 即在尾结点后插入新元素 linkedlist createlistt(int n) { int i = 0; node *t; t = (node *)malloc(sizeof(node)); t->next = null; node *r; r = t; int x; while(idata = x; r->next = p; r = p; i++; } r->next = null; return t; }
计算链表长度:
//calculate the length int calculatelength(linkedlist l) { int length = 0; node *p = l; while(p->next) { length++; p = p->next; } return length; }
在指定链表的指定索引处插入新值:
//insert element into index x int insertelementintox(linkedlist l,int index,int e) { node *p = l; int length = calculatelength(l); if(index<1||index>length+1){return error;} else { for(int i = 1;inext; } node *q = (node *)malloc(sizeof(node)); q->data = e; q->next = p->next; p->next = q; return ok; } }
通过索引删除指定链表中的元素:
//delete element by index int deleteelementbyindex(linkedlist l,int index) { int length = calculatelength(l); if(index<1||index>length){return error;} else { node *p = l; for(int i = 1;inext; } node *q = p->next; p->next = q->next; free(q); return ok; } }
遍历并打印链表中所有结点元素:
//遍历 void traversallist(linkedlist l) { node *p = l->next; while(p!=end) { printf("%d ",p->data); p = p->next; } printf("\n"); }
对两个链表做非递减归并:
linkedlist mergedecline(linkedlist la,linkedlist lb) { node *a = la->next; node *b = lb->next; free(la); free(lb); linkedlist lc = initlist(); node *temp = lc; while(a!=null&&b!=null) { if(a->data<=b->data) { temp->next = a; a = a->next; temp = temp->next; } else { temp->next = b; b = b->next; temp = temp->next; } } temp->next == null; if(a!=null){temp->next = a;} if(b!=null){temp->next = b;} return lc; }
删除给定链表中所有重复元素(对重复元素只保留其中一个):
//delete repeating node void deleterepeatingnode(linkedlist l) { node *p,*q,*r; p = l->next; if(p==null){return;} while(p->next) { q = p; while(q->next) { if(q->next->data==p->data) { r = q->next; q->next=r->next; free(r); } else { q = q->next; } } p = p->next; } }
将链表中的元素按从小到大进行排序:
//sort from small to large int sortfsl(linkedlist l) { if(l->next==null){return error;} else { node *r = l; node *p = r->next; node *q = p->next; while(p->next) { while(q) { if(p->data>q->data) { int e = p->data; p->data = q->data; q->data = e; q = q->next; } else { q = q->next; } } r = r->next; p = p->next; q = p->next; } return ok; } }
删除链表中所有元素值大于x的结点:
int deleteagtx(linkedlist l,int x) { if(l->next==null){return error;} else{ node *p = l; while(p->next) { if(p->next->data>x) { node *temp = p->next; p->next = p->next->next; free(temp); } else{ p = p->next; } } return ok; } }
将链表中所有负数前置并排序:
//负数在前排序 int negativepriority(linkedlist l) { if(l->next==null){return error;} else{ node *p = l; while(p->next) { if(p->next->data<0) { node *temp = p->next; p->next = temp->next; temp->next = l->next; l->next = temp; } else{p = p->next;} } return ok; } }
南京航空航天大学922部分真题:
//2014真题-数据结构6 int _2014_t6(linkedlist l) { if(l->next==null){return error; } else{ node *p = l; node *t = null; node *s = null; int count = 1; while(p->next) { if(count%2==0) { t = p->next; p->next = p->next->next; //关键步骤 t->next = s; s = t; } else{ p = p->next; } count++; } p->next = s; return ok; } } //2015真题数据结构6 int _2015_t6(linkedlist l) { if(l->next==null){return error; } else{ node *p = l->next; node *q = l->next; node *t = l; node *top = null; while(p->next) { while(q->next) { if(q->next->data>p->data) { p = q->next; t = q; q = q->next; } else{ q = q->next; } } t->next = t->next->next; p->next = top; top = p; t = l; p = q = l->next; } p->next = top; return ok; } } //2013真题数据结构6 int _2013_t6(linkedlist la,linkedlist lb) { if(la->next==null){return error;} else{ node *a = la; node *b = lb; int element; while(a->next) { element = a->next->data; while(b->next) { if(b->next->data==element){break;} else{b = b->next;} } if(b->next==null) { node *t = a->next; a->next = a->next->next; free(t); } else{a = a->next;} b = lb; } a = la; while(a->next) { node *p = la->next; int e; while(p->next) { if(p->next->data>a->next->data) { e = a->next->data; a->next->data = p->next->data; p->next->data = e; } p = p->next; } a = a->next; } return ok; } } //2011真题-数据结构24 int _2011_t24(linkedlist l) { if(l->next == null){return error;} else{ node *p = l; int element = p->next->data; while(p->next) { if(element>p->next->data) { element = p->next->data; } p = p->next; } p = l; while(p->next) { if(p->next->data==element) { node *t = p->next; p->next = p->next->next; free(t); break; } p = p->next; } return ok; } }
使用单链表实现数制转换(1-10进制):
//数制转换(1-10进制) void transcoder(int num,int r) { linkedlist l = initlist(); l->data = -1; node *top = null; int i; while(num>0) { i = num%r; top = (node *)malloc(sizeof(node)); top->data = i; top->next = l; l = top; num = num/r; } printf("the result is: "); while(top->data!=-1) { printf("%d ",top->data); top = top->next; } }
测试:
int main() { int n = 0; printf("please enter the length:\n"); scanf("%d",&n); linkedlist la = createlistt(n); printf("traversal the list a:\n"); traversallist(la); printf("please enter the length:\n"); scanf("%d",&n); linkedlist lb = createlistt(n); printf("traversal the list b:\n"); traversallist(lb); traversallist(mergedecline(la,lb)); //merge printf("please enter the length:\n"); scanf("%d",&n); linkedlist ld = createlistt(n); traversallist(ld); deleterepeatingnode(ld); //delete repeating node traversallist(ld); int index,element; printf("please enter the length:\n"); scanf("%d",&n); linkedlist le = createlistt(n); traversallist(le); printf("please enter the index:\n"); scanf("%d",&index); printf("please enter the element:\n"); scanf("%d",&element); insertelementintox(le,index,element); //insert element into index x traversallist(le); int index; printf("please enter the length:\n"); scanf("%d",&n); linkedlist lf = createlistt(n); traversallist(lf); printf("please enter the index:\n"); scanf("%d",&index); deleteelementbyindex(lf,index); //delete element by index traversallist(lf); printf("please enter the length:\n"); scanf("%d",&n); linkedlist lg = createlistt(n); traversallist(lg); sortfsl(lg);//sort from small to large traversallist(lg); int x; printf("please enter the length:\n"); scanf("%d",&n); linkedlist lh = createlistt(n); traversallist(lh); printf("please enter the value:\n"); scanf("%d",&x); deleteagtx(lh,x);//p3-3-2-3-1 删除所有元素值大于x的结点 traversallist(lh); printf("please enter the length:\n"); scanf("%d",&n); linkedlist li = createlistt(n); traversallist(li); negativepriority(li);//负数在前排序 traversallist(li); printf("please enter the length:\n"); scanf("%d",&n); linkedlist lj = createlistt(n); traversallist(lj); _2014_t6(lj);//2014真题-数据结构6 traversallist(lj); printf("please enter the length:\n"); scanf("%d",&n); linkedlist lk = createlistt(n); traversallist(lk); _2015_t6(lk);//2015真题-数据结构6 traversallist(lk); printf("please enter the length:\n"); scanf("%d",&n); linkedlist ll = createlistt(n); traversallist(ll); printf("please enter the length:\n"); scanf("%d",&n); linkedlist lm = createlistt(n); traversallist(lm); _2013_t6(ll,lm);//2013真题-数据结构6 traversallist(ll); printf("please enter the length:\n"); scanf("%d",&n); linkedlist ln = createlistt(n); traversallist(ln); _2011_t24(ln); traversallist(ln); //2011真题-数据结构24 int num; printf("please enter the num:\n"); scanf("%d",&num); printf("please enter the r:\n"); scanf("%d",&n); transcoder(num,n); return 0; }
下一篇: ZBrush怎么使用笔刷把球体变成头发?