你的浏览器版本过低,可能导致网站不能正常访问!
为了你能正常使用网站功能,请使用这些浏览器。

链表基本操作的实现

[复制链接]
巅峰残狼 发布时间:2014-12-2 17:33
本程序转自网络,特别感谢网友白光) c5 x2 Q; K8 o8 D+ `8 B
+ n6 V3 [" \; _0 P6 O
#include <stdio.h>
6 u0 ?6 J5 ~, a( D5 k  S! V& L( f#include <malloc.h>
" R8 w% M2 F- A+ O5 Z( P#define LEN sizeof(struct student)) k, q7 n! J% c8 \. \' ?- P" R! s
  w" d( G" U- R- p9 D) R+ T: h% s
/*----------------数据定义----------------------*/ - l, L# c, l& n& K
* C7 I2 i/ l- P" G) V, a3 C
//定义一个学生信息的结构体,包括学号,姓名和结构体类型的指针
7 k/ ~: \- ]1 v/ _0 T, r7 Kstruct student
8 L, F2 q; d. i{
, L, J& i& d. h' p    long num;                //学号 6 C/ J+ u+ B1 X' t5 _
    char name[128];            //姓名
7 n1 W% q0 H+ H( L5 [* q) Y0 c    struct student *next;    //结构体指针 4 o6 P+ g% \% x' U* A2 ]( I( w
};( M) {4 R4 ]# v" }3 L
5 ^. ^3 K1 z8 F% \
typedef struct student * stuNode;' h* c( d# w  @, C5 ?' I

' J0 Y( x( E( h. }9 |* \int n=0;                    //全局变量,记录链表的长度
7 e8 b4 C2 n: X( w9 M! h4 Y$ x5 K& S5 i
/*---------------函数声明---------------------*/
1 K% L4 k7 L& F7 Y5 J7 ^; Z, m" Z  g& v
stuNode Create();            //创建一个新的链表                     7 ^1 B4 \9 O2 k( N

' K+ m9 F; Q9 r/ h" {6 y2 X$ B+ ]void Print(stuNode head);    //通过传入的链表头指针打印整个链表 1 A) h; F* ?4 b1 E! W6 y
! L- e; K( d0 u  l6 o! F
stuNode Delete(stuNode head,int num);    //通过传入的链表头指针和学生学号删除节点   s# T9 z0 }8 {9 j3 p: l: q

; v2 f9 e  I3 k* ystuNode Insert(stuNode head,stuNode newStu);    //依照学生学号的顺序向链表中插入新元素
( n+ v( o8 I) ^
6 Y' l& W) Y- G+ v. W
+ o) Y: Q' v' V; \, ]/*---------------函数定义----------------------*/; a  [. y& V' t0 s2 A- v
" a" X( ^6 y' j: y  ~( @! M
struct student *Create()+ ?- N6 H, o' X  |5 w! ?3 V% [
{3 U$ b" [2 f5 y" |
    struct student *head,*p1,*p2;
. j/ e( }+ Q, d. `6 p8 x
! N( `' H) w6 v" f( h7 s    //开辟一个LEN大小的空间,并让p1,p2指针指向它 9 b' c+ K3 \, O3 P$ u) T8 p; u
    p2=p1=(struct student *)malloc(LEN);
& J. U( k! }& @    //将头指针置为NULL
. K, @$ t- T) P+ X    head=NULL;8 c: W1 [: a& G8 S5 W6 ~
# g& X% q% N; }3 w$ f
    //创建链表节点并给节点的元素赋值   Q4 I' J1 K$ k0 \. g
    printf("请输入学生的学号和姓名:");
: w6 }2 m6 v2 B1 A- f+ K; o    scanf("%ld %s",&p1->num,p1->name);+ P7 ~! u5 F( d
    while(p1->num!=0)
" z7 M: P% Q( a1 x- L6 f    {( k' m. k0 ~& g' O1 `: I
        n=n+1;
1 `: O. K* ?" A) L9 a8 k; ?# j6 g        if(NULL==head)
$ f" m& G2 p% h8 t8 Y; _        {# b5 [$ o2 I3 R0 a5 O( ^' U6 o
            head=p1;* d+ H" `/ ~( W" M$ ~0 n* _
        }
4 H& p. F2 p' k1 F        else1 C# [/ s9 l, ~/ R! H* e( Q5 b" |  Q2 u
        {6 T/ c% i5 ~4 T: W# ~: l* A& O' q
            p2->next=p1;( P$ s! H) v) v8 I5 o, Q8 J* R2 t
        }9 W/ B+ P3 |6 R; ?. j9 Q
        p2=p1;1 D0 x0 y; R/ x  t# `3 G
        p1=(struct student *)malloc(LEN);
7 A1 k' n/ E2 o8 ~6 j/ Y' b" t        printf("请输入学生的学号和姓名:");& s7 K( Y; K/ G
        scanf("%ld %s",&p1->num,p1->name);
3 X6 L& `& Q7 J- f    }* g$ i' |7 N8 X# z
    //将尾节点的指针置为NULL   @; q+ h% {  y( E
    p2->next=NULL;
+ y+ R3 X0 o; t, X+ |* c    return head;1 L% O3 |9 P# l; C" u, K4 o$ g
}
' A3 ]( @. o* {. e* j3 e: I' F2 S- t, V9 X6 m1 x
& C9 z+ f1 c0 h2 @4 S, p. N- ]
void Print(struct student *head)6 k7 I- n5 v3 \; Z) k: j3 ?
{: y/ \  L6 t" U5 }* g( ?; d  z7 [- p
    struct student * p;
& Z4 h- p& j8 c! e% E; B    p=head;
& O3 n- m( t/ `# R5 K5 f' N; Z
+ U# M& H  f5 i& ~" F    //判断链表是否为空 4 f6 x# F1 O& @% M4 L  n, r+ U
    if(NULL==head)! H' L2 L% g9 N8 @
    {
1 U2 i' k0 H- v& Y! v        printf("链表为空!\n");$ H# p' R: l; \, t/ f2 a2 l& k+ t
        return head;/ W8 b1 V( B4 l. [! v' u/ v8 h8 _
    }* E1 c$ g# G1 J% c" t
    else
: @8 @% {, {( _4 A8 V+ m: x    {/ o" z% M& p8 F0 X) `+ C" I. {
        //循环打印链表中的元素
, c. y' ?0 x  O/ r        printf("%d 个记录分别为:\n",n);
  o* ~- [6 N8 N! v        while(p!=NULL); i* ~( i% |/ O4 q- Q% F
        {
3 R  k4 n2 T6 Z0 S% e. n            printf("%ld %s\n",p->num,p->name);
9 M% m4 |5 i$ D: c" `5 s* O            //指针指向下一个节点 ) t+ Q& w- [; P& p" H/ f: Y- B4 M
            p=p->next;
6 y) l4 t$ p% m        }. r0 [0 g, t5 F
    }
# T& F0 O1 n. x& m}
# B! @* U; l$ c2 Q. m  g  P# E% c0 p" b0 h( U, u
' @  g/ N2 {9 \$ _9 M
struct student *Delete(struct student * head,int num)9 K) h# {4 M* J2 P( U" W( \3 I
{- q; j1 d, V0 B% T
    struct student *p1;
4 O6 p$ ]  y) g) B/ N8 E: l6 d    struct student *p2;
/ Y+ J3 r2 F+ l/ p    p1=head;! @. J) _6 C3 n- H
    //判断链表是否为空 7 i% D8 f, h' j1 h1 r
    if(NULL==head), c" j+ Z. T* C
    {7 T8 j3 Q: [% w8 F. B1 N
        printf("链表为空!\n");) O$ ~2 Q2 Y& g! i% I# Q
        return head;8 E7 F4 p( @5 D8 H% v- n1 {2 g) |
    }1 R! Z$ T; q+ }% r$ o& X
    //遍历节点,判断当前节点是不是需要删除的节点及是否为尾节点
) X* [; B* @- m: @    //如果找到相应节点,或者已经遍历到尾节点就跳出循环
- T: a, f3 A, N+ u2 Q    while(p1->num!=num&&p1->next!=NULL)9 t: [& w$ t/ A! ~5 P/ [* L8 H% g" {0 F
    {' b& a8 q1 v6 G8 a1 F
        p2=p1;
0 W6 n# L9 ^1 J$ b; q$ C        p1=p1->next;5 I6 f7 C. j8 k$ \. h
    }, G+ R  A# a$ ^7 b) l$ M* |
    //判断是否找到相应节点 ; e( W& Y0 X% l1 K$ u2 W8 f
    if(p1->num==num). P7 s4 |' v, {# s+ a5 D
    {: t% a) n( |. P2 s2 _
        //要删除的节点是不是链表的第一个节点
! ]& |% ^( E5 I% J# ]4 {        //如果是,就将头指针指向该节点的后一个节点/ `( Y8 b9 i7 F
        //如果不是,就将该节点的前一个节点的指针指向该节点的后一个节点
: P9 A) j( w5 ^3 N( T- W        if(head==p1)
( e: c& Z" l8 ~' ^: s' ~        {2 d1 \) L  U& {( s0 F) ^8 {
            head=p1->next;4 n2 `2 ]- [9 ^/ ~& @6 a
        }+ T( ]2 t# b. Q* c( Y
        else
7 B% G) i3 O" _+ f; f        {, I8 r$ l8 ?1 {: W/ C
            p2->next=p1->next;
5 `& w- M! U  p! c* N4 K        }
+ G0 ?5 e  |) D5 S        n=n-1;
% y: Y) C' l- |9 J/ y% s% C/ u' X        printf("%ld 节点已删除.\n",num);/ }  V( o: ~) ]& _
    }
1 u, D, m# v% c3 W. N& d  _    else
. j8 [( p* s$ ^- l- s" C! }0 X, Y    {
5 _* d: V+ ^% z/ o* P4 O' H        printf("链表中没有要删除的元素.\n");
) u. q0 |' N3 K  T+ b' M/ C    }
3 j6 S. n& U1 {2 s    return head;$ I7 [% @( G& @/ L$ M
}: n, ^  C* @* \! x* }

1 a9 u% \4 [  q! P# p9 ?/ ]
  k7 N6 f7 \/ @7 ~struct student *Insert(struct student * head,struct student * newStu)
- b" l6 N% H# l% D- ~{4 v! Z0 H0 l8 k$ E" f8 y4 E
    struct student *p0;4 H, H. H8 L" `; f- P
    struct student *p1;- T: F4 R- L- C9 x
    struct student *p2;% U$ C; S, _! d( A/ {
    p0=newStu;
$ L( A3 g% b4 z    p1=head;+ i# i% E. i0 {9 K* V6 l
    //判断链表是否为空,如果是空链表,就将新节点作为第一个节点 ( j9 ?/ |; f9 V* X5 K" U9 z+ w5 o
    if(NULL==head)3 k2 B' X- c- V( P
    {
2 ]8 G$ r, r' G/ n7 q) `' M        head=p0;6 Q  \5 W7 o0 \4 M9 }8 w) m
        p0->next=NULL;
( K1 C1 O- c  E! `1 U7 o* I  M  Z    }
( ?4 M/ E" m& f% Q2 S    else; x* V: ^+ a7 e; x8 v& j
    {
2 m: L! e/ k5 X% A        //遍历每一个节点中的学号,与新学号比较大小
4 n5 E6 e+ A4 y# p( a        //如果找到一个学号比新学号大,就将新学号的节点插入它之前 ' F, A; K9 v0 f, K' O, f( [
        //如果尾节点的学号仍比新学号小,就将新节点插入到链表尾部
+ }& [8 J" C: O# Y% d2 |& a        while((p0->num > p1->num)&&(p1->next!=NULL))% M; ^2 s$ |( Y: G5 k, k* g
        {5 j3 X% u! u, h- L/ H0 B. X+ t
            p2=p1;% N, t$ _0 b' `' v/ N& A  E" Z' g: L
            p1=p1->next;
1 Q% ?" K. I, v) @0 n        }
) j- P0 a; ]  k+ g5 z        //找到一个比新学号大的节点
, j5 K- y4 F% C! X5 p: f& Q) e        if(p0->num <= p1->num)6 j/ Y% I/ X0 L2 U
        {
) ^& c; N. f# O' K! ?            //判断该节点是否为头节点,如果是,则将新节点设置为头节点
8 Q2 Y) h$ o% z2 d' z0 p            if(p1==head)
9 i' x, `" u8 `" r: U) N  }            {8 q5 T8 `  w2 X+ a2 C0 b5 r$ u
                head=p0;
, d' m/ e3 c  B: P9 c" x8 p            }
$ ^3 c8 c. ?1 _3 l4 v            else
8 ~% g/ X- P3 l6 F4 H            {# ]* e! X& m: v, i7 u  O, N. V
                p2->next=p0;/ e. |2 C, ^; F0 v) [2 S% K6 j
            }' y4 ?8 `& j) _( |" e* l, r
              p0->next=p1;
) E  F' U( G8 Y' h+ X% n; E        }
0 ?% d  _# D# ]% G        else# q+ T( Q1 }: j6 i
        {
9 ^" A( j) P/ [9 a            p1->next=p0;
1 Q4 a) l+ c( G, O            p0->next=NULL;4 I+ q4 n5 A( v# q; h( G- N
        }
  N9 M* ~) t7 H5 F    }
3 \6 w! s' c. R+ i    //链表长度加1
" |) |4 g' M" X% C2 H    n=n+1;
5 f; I5 N( i& G    printf("%ld 插入成功!\n",newStu->num);, F" f5 Y# j+ A* {6 x& W
    return head;
3 I9 U9 `2 T8 }- N}5 ?6 o0 T" n$ M2 l
; D2 w7 J1 \  O3 L
void main()# E7 \0 t" |! ?1 Z% E6 ^9 O
{8 m# x) \6 ?, H3 [
    struct student *head;
' j9 n6 P; r& N7 z' F    struct student *stu;# K+ @2 L' H' U/ _7 U) y/ ~" [
    int num;
, Y, k/ D4 ]6 N2 _- V/ @    head=Create();- a+ d! h5 G- N) V. C
    Print(head);* |9 a9 ^! \9 `3 w$ ]
    printf("请输入要删除的学号:");
/ [9 |* ]% Z; {0 h" s2 O  P    scanf("%ld",&num);
' |" r  k) a4 T7 ^9 [* K    while(num!=0)) [  y2 [( T7 n
    {' u) }- R! W9 s) S0 {, p
        head=Delete(head,num);/ s( R$ ]/ i* }; l5 F
        Print(head);1 c( p/ O' n2 |% D6 ?
        printf("请输入要删除的学号:");) X! {4 r' U7 G" b; y$ y; W: A- q
        scanf("%ld",&num);' a. Y, T+ u: i1 g1 K$ q; n- u0 S
    }
( k: y$ j5 x, z) O    printf("请输入要插入的节点:");
' ]( l& K$ B0 i& B' [) F/ e( f    stu=(struct student *)malloc(LEN);; ]7 W/ ~6 Y" o: A7 P- R
    scanf("%ld %s",&stu->num,stu->name);/ [0 G; m" f7 ?4 Q' S5 h1 A
    while(stu->num!=0)
$ W  L' M4 T4 N    {; C/ s; c; H0 O: p6 [
        head=Insert(head,stu);  M. Z0 E$ N  @
        printf("请输入要插入的节点:");. O! N2 {# g6 R9 c
        stu=(struct student *)malloc(LEN);
$ A& n! a% y# V' ~4 h% m        scanf("%ld %s",&stu->num,stu->name);5 z: d4 K4 D7 H; Z0 r5 \
    }
! e( ?7 p2 Y7 X6 [0 \/ M  {* p+ ~    Print(head);+ r7 ~. J" M9 L: _% m
}# v' d9 @4 ~5 Y7 J4 \
, D4 R, L) S8 U: E
赞 收藏 1 评论4 发布时间:2014-12-2 17:33

举报

4个回答
霹雳之火 回答时间:2014-12-3 22:26:28
链表太常用了,顶起
沐紫 回答时间:2014-12-4 13:19:26
支持版主大大!
木易-357428 回答时间:2015-1-9 15:17:37
支持一下版主
花落成尘眼泪 回答时间:2018-11-30 13:09:22
正在学链表,帖子真心不错,要是楼主能够分享整个工程模板,那就对我们部分小白太好了
关于
我们是谁
投资者关系
意法半导体可持续发展举措
创新与技术
意法半导体官网
联系我们
联系ST分支机构
寻找销售人员和分销渠道
社区
媒体中心
活动与培训
隐私策略
隐私策略
Cookies管理
行使您的权利
官方最新发布
人形机器人运动控制、感知与智能配电
半导体创新技术与应用方向
EE架构与软件定义汽车
12V/48V 汽车智能配电(SPD)
区域控制单元(ZCU)与分区架构
关注我们
st-img 微信公众号
st-img 手机版