链表基本操作的实现

巅峰残狼 · 2014-12-02T09:33:54+00:00

本程序转自网络，特别感谢网友白光0 v2 \& c/ T! _4 x * @% u# |6 S& ~# x$ x #include ( R( X& ]8 _& `8 S6 X0 E9 S% P Y* G #include 2 U8 n) Z% w2 c& }' X$ w #define LEN sizeof(struct student)7 R6 Z2 E4 Q8 N6 i! q9 d + l! e# H& t' }& Y6 f3 g" C/*----------------数据定义----------------------*/ 9 X5 D5 \6 x6 ?3 Z2 @, j6 O ) A6 }) Q f" G" Y( D4 J- ] //定义一个学生信息的结构体,包括学号,姓名和结构体类型的指针 * ^8 E e* l/ Rstruct student0 Y$ ^$ B. s7 r( c5 g4 ~& c& Y {3 S% F- Y: x) b7 \' E/ U& S long num; //学号 * `" I/ C# P! M, E+ K char name[128]; //姓名 * v/ }) R. F$ N# N& I8 b) Q struct student *next; //结构体指针 $ O; W9 R; `" _8 `# f/ y" b};* u( o- i; z: _, i / T% Y6 W2 W% h2 E! u0 B: k/ V; j7 Utypedef struct student * stuNode;/ e$ J! T& ~0 Z J; w7 A W # f* `) Z8 g7 n* vint n=0; //全局变量,记录链表的长度 ) Q# e' F( y5 J ( v! c: w1 M2 I6 v; B3 B) s/*---------------函数声明---------------------*/+ N; a+ q( v+ s( V, O. s 3 E7 v) H4 `/ \5 l6 ^ stuNode Create(); //创建一个新的链表 7 z1 c+ z0 s% i, I, I8 q/ d* D' P! O/ v void Print(stuNode head); //通过传入的链表头指针打印整个链表 I4 V9 J; ^% f) h$ G9 F 2 X4 [( W& M1 P+ [+ RstuNode Delete(stuNode head,int num); //通过传入的链表头指针和学生学号删除节点 ; R$ O" r0 a1 G7 [& e ! M, U4 Z5 A4 [0 e% g6 s4 N( }stuNode Insert(stuNode head,stuNode newStu); //依照学生学号的顺序向链表中插入新元素 4 C) v* _$ y2 `6 x6 \# u* [" `' _" k 9 Y$ b8 P1 z* m7 J) T0 W% ~ 6 d2 @: ~# S9 f$ N/*---------------函数定义----------------------*/% u, o4 ]2 |. V F5 g ; f0 F$ _/ @% t% G7 \ struct student *Create()1 e! ]3 ?# Y% b6 q5 N0 n; p { . \' k! j( {+ B6 t$ L struct student *head,*p1,*p2;5 M/ i o. }) y/ d# }# V ! _' G' z9 b# I( c //开辟一个LEN大小的空间,并让p1,p2指针指向它 . v X3 ]& R6 A5 m3 o$ N p2=p1=(struct student *)malloc(LEN); I" o- `* Z, L8 a$ P" a; V //将头指针置为NULL : V. f: Q# `; v& b% I head=NULL;- K: I- `: C! x$ i ; i$ Z) M; ]9 S4 B+ ~& ?9 g1 h6 Y1 i: | //创建链表节点并给节点的元素赋值 " P! f# s# j5 q printf("请输入学生的学号和姓名:");' Y9 M0 \ g1 n, j scanf("%ld %s",&p1->num,p1->name); ; K* @8 b* s, p. K6 T, C. h( V4 x while(p1->num!=0)$ h1 u% Y; B3 d$ \' @0 u0 A; v, E {4 ~" r9 [- W* m6 s4 r* ~" Z n=n+1;( `: W2 O D" C S$ h+ g/ _5 _% C if(NULL==head)% o# u- P. |; ?% w/ ~ { % m8 O' L* |7 I7 |/ Y' N2 Q head=p1; % L" J- B0 h# o( J" @; V }( y' I3 A8 j- I, @ else & C- s( X3 A& g) `2 |7 v D7 m! k { " \# a. C" }( _ p2->next=p1; 1 B. T! _) w" ^/ x9 n2 M } ; K i+ k, O2 `& j; z4 Y p2=p1; ; p% w% p. b7 j) i2 f5 p p1=(struct student *)malloc(LEN);) v A& l7 z2 `+ e/ X" ]" `, @ printf("请输入学生的学号和姓名:");% n, ^% y# E" l4 T' p scanf("%ld %s",&p1->num,p1->name); 5 `& ^0 [ Z" A C' F }+ K# o0 `+ H* |! k9 i; k% [ //将尾节点的指针置为NULL " z/ R( \9 H/ n, h- V p2->next=NULL; $ S( H8 q& i* d9 J6 G( c! Q* x return head; + i! F4 @: J& @}* c! I' Q S; K% X4 G* I+ j 9 e; E' d3 e6 G( ~! P8 Y . @! Z, ^( w* Z: _void Print(struct student *head)$ u" y( i! C; Y8 j$ F9 ^3 N* s { d! W0 M2 p0 n2 h struct student * p; W2 ]: X- s4 k! a* J p=head; 0 S; G( M( G( _$ L % O% r" ^$ q& W; J //判断链表是否为空 8 a( r& \: T+ b! V$ X% C if(NULL==head)8 x5 w" V# k: e1 V { 2 v" m8 l ~+ W* y, d printf("链表为空!\n"); 9 x9 f4 N8 T- a return head; $ ^9 d8 `; w6 G6 B% V } ( U4 E" Z! N' V# A- f else + [& N( I# N$ j) m- m0 R { - @; B" G' ]. h1 ]2 k //循环打印链表中的元素 2 K) }5 ]+ O# c8 L% o1 p printf("%d 个记录分别为:\n",n);8 V2 D/ W2 v p+ R: J while(p!=NULL) 6 I/ U* \' h4 Z- X {2 l4 n- o) [8 r0 I9 t printf("%ld %s\n",p->num,p->name);9 x8 H! K3 i/ j5 F% o' w //指针指向下一个节点 % P0 E5 Z! a0 f2 g p=p->next; " E0 g! v$ A& ~$ N3 T } & V% `% b. J4 T' ^! Q1 n } $ G% J& C. _. _! T) k* e}' [" t; @" E/ p/ u' Q* q ( _2 R) V, ?5 z6 u! `" F) s - e' Q, T5 T; X$ |struct student *Delete(struct student * head,int num) ' L4 w! Q, N/ D' V# } q{# Z5 N$ B" m% I( w n) ^ struct student *p1; * X$ J4 C, `2 ]9 j! h! \8 m& O struct student *p2; 2 r! r3 p6 M- x p1=head;# |; `8 o% n: C2 [! a2 d //判断链表是否为空 ) p& S6 q% C* F, q& z if(NULL==head)4 o# Y: k e9 }# X {4 ^4 G- ]+ c* u. K$ e8 u7 u printf("链表为空!\n");) O/ T! s z* b+ } return head;( j' X7 T, N* j5 ?$ y- i- ~9 d( M } 2 `7 n; S2 B) D* T* b* ^ //遍历节点,判断当前节点是不是需要删除的节点及是否为尾节点 4 ^$ @( Y2 P; R0 @ //如果找到相应节点,或者已经遍历到尾节点就跳出循环 * W+ o# L, j2 L$ H0 X while(p1->num!=num&&p1->next!=NULL) 9 D1 |( U9 Q. q5 u# ?. u- _ { " Y O! A' B8 X* a2 h0 X" g p2=p1;) V: C$ x$ W; d% b% M4 H p1=p1->next; " Y! N! R/ J9 y9 p# s; K4 _ } 5 F5 }2 E# j( q" h& O" a //判断是否找到相应节点 . [+ T9 S4 O) V1 k if(p1->num==num)4 B7 K8 i6 l, h) r { Q5 N8 J' Y: X1 S. s/ p //要删除的节点是不是链表的第一个节点/ I- [ {6 U" ~, n( ?- j //如果是,就将头指针指向该节点的后一个节点 # | F: R8 E+ K# B0 r' R //如果不是,就将该节点的前一个节点的指针指向该节点的后一个节点 , i- P/ _* i. M j if(head==p1)+ k4 ]* x, d6 j/ B- i { 7 c) n! J* V5 `) b6 O, [4 \2 \ head=p1->next; 9 @7 w9 U# g+ ]( b }( @4 ^. U9 ]8 r' ?" c) B, C3 K else# L* y; I( R, W: d {3 U! {: y2 I' d: c p2->next=p1->next;, i4 p; W: k0 R }" V" G5 p) _1 [7 \* [3 M n=n-1;9 m1 r% h" S3 I6 u% t printf("%ld 节点已删除.\n",num);5 k4 Z; r/ E* k$ Y) s& l, d! j } ' s( d6 o% w& z( M else0 l9 e0 Z3 P- [* [# [$ U* j$ p- { {$ V7 G" ^# m" _3 e# m. } printf("链表中没有要删除的元素.\n");- R* R% t0 l$ Q/ N }% ?4 V, U5 k& Q, e& ^& N( [ return head;: A' o' e( {0 ^6 t* P$ D } ; \: ^- j/ m1 K4 r6 P2 u m $ G8 a4 r. {- b! Y3 p' l" d: v* m$ r( ]3 i struct student *Insert(struct student * head,struct student * newStu) 3 P- h1 J; `# E( ]( |& r1 S{4 \9 J" [# @( ]" w% Q$ ]0 V struct student *p0;& R$ y) D& e2 U- t6 Z& |4 \ struct student *p1; / T9 Z! n$ b; s' w3 y l' w2 I struct student *p2; ; A* `$ Y. u5 @7 a Y5 N p0=newStu; ( B) {% O5 p3 a# H5 H+ }" O. K p1=head; : v5 _0 _. L, E" Z B5 Y, W" @. b6 X //判断链表是否为空,如果是空链表,就将新节点作为第一个节点 : _& J/ ?% y; ?9 @: Z" @8 Y( O4 V if(NULL==head) : ^/ K0 ]" D {0 e {8 h4 j: A4 c# H+ J& e head=p0;$ z' j, I `- v* a8 D7 U/ g p0->next=NULL; ( E+ {5 }7 N+ U, J } 0 p& [& n' y8 P; w# I else) @* X; k. H% |+ O0 `: L& L {. d; E. A/ k1 f" J& S //遍历每一个节点中的学号,与新学号比较大小 2 i' W+ w7 D; i2 N2 D% u+ ~- Z4 _$ [( ~ //如果找到一个学号比新学号大,就将新学号的节点插入它之前 - x, P( [2 p- ]0 Z$ X7 e //如果尾节点的学号仍比新学号小,就将新节点插入到链表尾部 " e c% f* C6 u2 X: T' \% A( j while((p0->num > p1->num)&&(p1->next!=NULL))- [: q: I1 \$ R {( ^$ G0 A4 B. U, b( T2 L p2=p1; e" f/ h& @/ q: U( K. J p1=p1->next;8 r% o. s3 A+ N6 k3 k! N } - Q/ i+ |, q6 L* p& I //找到一个比新学号大的节点 ' p$ V$ T( d5 g, B) l4 }9 b if(p0->num num)- k$ K0 k5 p' q! ]7 b8 _" S3 A, v {" b" E3 |% ?' W+ U //判断该节点是否为头节点,如果是,则将新节点设置为头节点 $ Z4 s. ?) ]3 T if(p1==head)5 b; e6 E+ s7 |- V( }7 ?1 ` {; T& b( @" S' i; m( ^ head=p0; : @0 j3 r ^9 M* {4 M } ) t% e2 l! K3 l5 Q else ; `- S) [. t. n; E, b% T" F9 G { 5 n; L z: ?7 X& J; p/ g& u0 W# \% y p2->next=p0; ' O' I8 ^9 t# E/ d7 N& T } / I% l" t& Q7 G8 A p0->next=p1;0 s+ n8 }$ m I% D+ m8 { } 4 }6 k3 F7 j; i; g' V# K" h' P, p else ~ O5 ~4 ?% G0 [. t0 v% p { . J) ? G3 V3 G, F p1->next=p0; 8 A9 D3 o+ {) v p0->next=NULL; 2 C; X2 O! ]0 S5 V7 t ` }; {- P P3 M4 Q6 ^$ W } 0 m M% f* \! P( X //链表长度加1 + H ^- J# @% e- |7 b9 Y n=n+1; % Z$ c1 ~/ x7 p- t5 j; r printf("%ld 插入成功!\n",newStu->num);! A9 y) O/ c+ n m: ^ return head; " s% ]# S2 ]! ?( L7 U$ K; Q} ( `5 F2 O2 W5 X' m# i5 Q$ f8 |$ Z$ c$ A+ g) v% N void main()$ y5 Z, [/ a, t" g) V& K5 G { + I* z- z+ ^4 U: h& P% F2 @; Z2 C t" o struct student *head;: R! E# J1 P# ?7 N l& }) J* V7 z struct student *stu; 1 e/ [& p& S: A4 h% v7 y* o int num;% e# w7 @( m+ H1 ~ head=Create();- _# E, X3 l r$ V. @( c Print(head);2 z3 F5 |5 Y7 q8 e M5 i printf("请输入要删除的学号:"); / K# e/ ^4 w; N0 C0 I scanf("%ld",&num); 1 @5 x" m4 F; l ] A while(num!=0) _* C1 h3 Q6 v { ( g+ j! ^! f+ K0 ~$ i head=Delete(head,num); / C+ a* M( F& j Print(head); ' u! x7 S- T# h1 h8 p) l8 S printf("请输入要删除的学号:"); 1 e9 W; m' S: }1 J# y$ P7 H scanf("%ld",&num);* Y- V2 P ~+ ?, O' t } 0 c4 n; {1 n5 o4 z printf("请输入要插入的节点:"); ) ]5 O( @! J. v: w8 k7 L$ D stu=(struct student *)malloc(LEN);9 {0 @6 i2 t1 ?4 j; A. J" C scanf("%ld %s",&stu->num,stu->name);+ V T5 L8 A; a; z( i/ y while(stu->num!=0) 9 o1 d. t# A6 \" | { + [+ g0 e: H; ?+ G head=Insert(head,stu);- w8 i- ]/ T2 F/ a) e printf("请输入要插入的节点:"); , c! [* J% V4 y: o- H stu=(struct student *)malloc(LEN); 0 n) a, @3 H; R scanf("%ld %s",&stu->num,stu->name); 3 ]7 o7 x5 X: ]4 Y: h }( J- B/ M& v8 m. |; [# } Print(head);+ l- ~' }3 k4 S }4 T" V4 x/ k" B+ o$ l + X E" s2 ?% {" r+ r

[复制链接]

巅峰残狼发布时间：2014-12-2 17:33

技术帖
文章封面:	-
文章简介:	-

本程序转自网络，特别感谢网友白光

#include <stdio.h>
#include <malloc.h>
#define LEN sizeof(struct student)

/*----------------数据定义----------------------*/

//定义一个学生信息的结构体,包括学号,姓名和结构体类型的指针
struct student
{
long num;             //学号
char name[128];          //姓名
struct student *next; //结构体指针
};

typedef struct student * stuNode;

int n=0;                   //全局变量,记录链表的长度

/*---------------函数声明---------------------*/

stuNode Create();          //创建一个新的链表

void Print(stuNode head); //通过传入的链表头指针打印整个链表

stuNode Delete(stuNode head,int num); //通过传入的链表头指针和学生学号删除节点

stuNode Insert(stuNode head,stuNode newStu); //依照学生学号的顺序向链表中插入新元素

/*---------------函数定义----------------------*/

struct student *Create()
{
struct student *head,*p1,*p2;

//开辟一个LEN大小的空间,并让p1,p2指针指向它
p2=p1=(struct student *)malloc(LEN);
//将头指针置为NULL
head=NULL;

//创建链表节点并给节点的元素赋值
printf("请输入学生的学号和姓名:");
scanf("%ld %s",&p1->num,p1->name);
while(p1->num!=0)
{
      n=n+1;
      if(NULL==head)
      {
         head=p1;
      }
      else
      {
         p2->next=p1;
      }
      p2=p1;
      p1=(struct student *)malloc(LEN);
      printf("请输入学生的学号和姓名:");
      scanf("%ld %s",&p1->num,p1->name);
}
//将尾节点的指针置为NULL
p2->next=NULL;
return head;
}

void Print(struct student *head)
{
struct student * p;
p=head;

//判断链表是否为空
if(NULL==head)
{
      printf("链表为空!\n");
      return head;
}
else
{
      //循环打印链表中的元素
      printf("%d 个记录分别为:\n",n);
      while(p!=NULL)
      {
         printf("%ld %s\n",p->num,p->name);
         //指针指向下一个节点
         p=p->next;
      }
}
}

struct student *Delete(struct student * head,int num)
{
struct student *p1;
struct student *p2;
p1=head;
//判断链表是否为空
if(NULL==head)
{
      printf("链表为空!\n");
      return head;
}
//遍历节点,判断当前节点是不是需要删除的节点及是否为尾节点
//如果找到相应节点,或者已经遍历到尾节点就跳出循环
while(p1->num!=num&&p1->next!=NULL)
{
      p2=p1;
      p1=p1->next;
}
//判断是否找到相应节点
if(p1->num==num)
{
      //要删除的节点是不是链表的第一个节点
      //如果是,就将头指针指向该节点的后一个节点
      //如果不是,就将该节点的前一个节点的指针指向该节点的后一个节点
      if(head==p1)
      {
         head=p1->next;
      }
      else
      {
         p2->next=p1->next;
      }
      n=n-1;
      printf("%ld 节点已删除.\n",num);
}
else
{
      printf("链表中没有要删除的元素.\n");
}
return head;
}

struct student *Insert(struct student * head,struct student * newStu)
{
struct student *p0;
struct student *p1;
struct student *p2;
p0=newStu;
p1=head;
//判断链表是否为空,如果是空链表,就将新节点作为第一个节点
if(NULL==head)
{
      head=p0;
      p0->next=NULL;
}
else
{
      //遍历每一个节点中的学号,与新学号比较大小
      //如果找到一个学号比新学号大,就将新学号的节点插入它之前
      //如果尾节点的学号仍比新学号小,就将新节点插入到链表尾部
      while((p0->num > p1->num)&&(p1->next!=NULL))
      {
         p2=p1;
         p1=p1->next;
      }
      //找到一个比新学号大的节点
      if(p0->num <= p1->num)
      {
         //判断该节点是否为头节点,如果是,则将新节点设置为头节点
         if(p1==head)
         {
            head=p0;
         }
         else
         {
            p2->next=p0;
         }
            p0->next=p1;
      }
      else
      {
         p1->next=p0;
         p0->next=NULL;
      }
}
//链表长度加1
n=n+1;
printf("%ld 插入成功!\n",newStu->num);
return head;
}

void main()
{
struct student *head;
struct student *stu;
int num;
head=Create();
Print(head);
printf("请输入要删除的学号:");
scanf("%ld",&num);
while(num!=0)
{
      head=Delete(head,num);
      Print(head);
      printf("请输入要删除的学号:");
      scanf("%ld",&num);
}
printf("请输入要插入的节点:");
stu=(struct student *)malloc(LEN);
scanf("%ld %s",&stu->num,stu->name);
while(stu->num!=0)
{
      head=Insert(head,stu);
      printf("请输入要插入的节点:");
      stu=(struct student *)malloc(LEN);
      scanf("%ld %s",&stu->num,stu->name);
}
Print(head);
}