鏈表及位運算

鏈表處理──結(jié)構(gòu)指針的應(yīng)用一、概述1、鏈表的定義

鏈表是一種最簡單、最常見的動態(tài)數(shù)據(jù)結(jié)構(gòu)，它通過指針（鏈）將一組節(jié)點連接在一起。

節(jié)點的定義

節(jié)點包括兩部分：信息部分和鏈接節(jié)點的指針 例如：使用節(jié)點描述一個學(xué)生的信息（姓名）

structnode{ char name[20]; /*信息*/

structnode*link; /*指針*/ }; 鏈表組成

?指向鏈表表頭節(jié)點的指針(頭指針，也稱為head)

?表節(jié)點（數(shù)據(jù)節(jié)點，也稱為節(jié)點，保存數(shù)據(jù)信息）每個結(jié)點由2個域組成：1）數(shù)據(jù)域──存儲結(jié)點本身的信息。

2）指針域──指向后繼結(jié)點的指針。尾結(jié)點的指針域置為“NULL（空）”，作為鏈表結(jié)束的標志。1249C1021D1500ENULLB1475A1356表頭指針（head）數(shù)據(jù)節(jié)點數(shù)據(jù)節(jié)點15001021147512491356鏈表的圖示表示二、定義節(jié)點的結(jié)構(gòu)，說明表頭指針 根據(jù)節(jié)點實際需要保存的信息，定義節(jié)點的結(jié)構(gòu)。包括信息部分和鏈接結(jié)點的指針

例如：定義一個描述學(xué)生信息（姓名/住址/電話）的節(jié)點

typedef

structnode {charname[20],address[20],phone[15];/*信息*/

structnode*link;/*指針*/ }NODE; /*定義節(jié)點*/

NODE*head; /*說明頭指針head*/在Ｃ語言中，用結(jié)構(gòu)類型來描述結(jié)點結(jié)構(gòu)。例：建立和輸出一個簡單鏈表#defineNULL0structstudent{longnum;floatscore;

structstudent*next;};main(){structstudenta,b,c,*head,*p;a.num=99101;a.score=89.5;b.num=99103;b.score=90;c.num=99107;c.score=85;/*對結(jié)點的num和score成員賦值*/head=&a;/*將結(jié)點a的起始地址賦給頭指針head*/head99101

89.5a99103

90b99107

85

ca.next=&b;/*將結(jié)點b的起始地址賦給a結(jié)點的next成員*/b.next=&c;/*將結(jié)點c的起始地址賦給b結(jié)點的next成員*/c.next=NULL;/*c結(jié)點的next成員不存放其他結(jié)點地址*/p=head;/*使p指針指向a結(jié)點*/do{printf(“%ld,%5.1f\n”,p->num,p->score);/*輸出p指向的結(jié)點的數(shù)據(jù)*/p=p->next;/*使p指向下一結(jié)點*/}while(p!=NULL);/*輸出完c結(jié)點后p的值為NULL*/}

NUllp三、對鏈表的基本操作1、對鏈表的基本操作有：創(chuàng)建、檢索（查找）、插入、刪除和修改等。（1）創(chuàng)建鏈表是指，從無到有地建立起一個鏈表，即往空鏈表中依次插入若干結(jié)點，并保持結(jié)點之間的前驅(qū)和后繼關(guān)系。（2）檢索操作是指，按給定的結(jié)點索引號或檢索條件，查找某個結(jié)點。如果找到指定的結(jié)點，則稱為檢索成功；否則，稱為檢索失敗。（3）插入操作是指，在結(jié)點ki-1與ki之間插入一個新的結(jié)點k’，使線性表的長度增1，且ki-1與ki的邏輯關(guān)系發(fā)生如下變化：插入前，ki-1是ki的前驅(qū)，ki是ki-1的后繼；插入后，新插入的結(jié)點k’成為ki-1的后繼、ki的前驅(qū)。（4）刪除操作是指，刪除結(jié)點ki，使線性表的長度減1，且ki-1、ki和ki+1之間的邏輯關(guān)系發(fā)生如下變化：刪除前，ki是ki+1的前驅(qū)、ki-1的后繼；刪除后，ki-1成為ki+1的前驅(qū)，ki+1成為ki-1的后繼。第8章位運算所謂位運算是指，按二進制位進行的運算。

8.1

位運算和位運算符

8.2

位運算舉例

8.1位運算一、位運算及其運算符

1．按位與──&

(1)格式：x&y

(2)規(guī)則：對應(yīng)位均為1時才為1，否則為0：3&9=1。例如，3&9=1：0011&1001 ──── 0001=1 (3)主要用途：取(或保留)1個數(shù)的某(些)位，其余各位置0。

2．按位或──

|

(1)格式：x|y

(2)規(guī)則：對應(yīng)位均為0時才為0，否則為1：3|9=11。例如，3|9=11：0011 |1001──── 1011=11

(3)主要用途：將1個數(shù)的某(些)位置1，其余各位不變。

3．按位異或──^(1)格式：x^y(2)規(guī)則：對應(yīng)位相同時為0，不同時為1：3^9=10。(3)主要用途：使1個數(shù)的某(些)位翻轉(zhuǎn)(即原來為1的位變?yōu)?，為0的變?yōu)?)，其余各位不變。4．按位取反──~(1)格式：~x(2)規(guī)則：各位翻轉(zhuǎn)，即原來為1的位變成0，原來為0的位變成1：在IBM-PC機中，~0＝0xffff，~9=0xfff6。(3)主要用途：間接地構(gòu)造一個數(shù)，以增強程序的可移植性。5．按位左移──<<(1)格式：x<<位數(shù)(2)規(guī)則：使操作數(shù)的各位左移，低位補0，高位溢出：5<<2=20。6．按位右移──>>(1)格式：x>>位數(shù)(2)規(guī)則：使操作數(shù)的各位右移，移出的低位舍棄；高位：1)對無符號數(shù)和有符號中的正數(shù)，補0；2)有符號數(shù)中的負數(shù)，取決于所使用的系統(tǒng)：補0的稱為“邏輯右移”，補1的稱為“算術(shù)右移”。例如，20>>2=5。說明：（1）x、y和“位數(shù)”等操作數(shù)，都只能是整型或字符型數(shù)據(jù)。除按位取反為單目運算符外，其余均為雙目運算符。（2）參與運算時，操作數(shù)x和y，都必須首先轉(zhuǎn)換成二進制形式，然后再執(zhí)行相應(yīng)的按位運算。例如，5<<2=20：0101→10100，20>>2=5：10100→00101。（3）實現(xiàn)&、|、^運算主要用途的方法

1）構(gòu)造1個整數(shù)：該數(shù)在要?。ɑ虮Ａ簦┑奈?、或要置1的位、或要翻轉(zhuǎn)的位上為1，其余均為0。

2）進行按位與、或按位或、或按位異或操作。（4）實現(xiàn)按位取反主要用途的方法

1）求~0，間接地構(gòu)造一個全1的數(shù)；

2）按需要進行左移或右移操作，構(gòu)造出所需要的數(shù)?；舅悸罚海?）使變量num右移8位，將8～11位移到低4位上。（2）構(gòu)造1個低4位為1、其余各位為0的整數(shù)。（3）與num進行按位與運算。/*程序功能：輸出一個整數(shù)中由8～11位構(gòu)成的數(shù)*/main(){intnum,mask;

printf("Inputaintegernumber:");

scanf("%d",&num);num>>=8; /*右移8位，將8～11位移到低4位上*/mask=~(~0<<4); /*間接構(gòu)造1個低4位為1、其余各位為0的整數(shù)*/

printf("result=0x%x\n",num&mask);}

8.2應(yīng)用舉例[例11.1]從鍵盤上輸入1個正整數(shù)給int變量num，輸出由8～11位構(gòu)成的數(shù)（從低位、0號開始編號）。程序運行情況：Inputaintegernumber:1000←┘result=0x3程序說明：~(~0<<4)按位取0的反，為全1；左移4位后，其低4位為0，其余各位為1；再按位取反，則其低4位為1，其余各位為0。這個整數(shù)正是我們所需要的。#include"stdio.h"main(){intnum,mask,i;

printf("Inputaintegernumber:");

scanf("%d",&num);mask=1<<15;/*構(gòu)造1個最高位為1、其余各位為0的整數(shù)(屏蔽字)*/

printf("%d=",num);for(i=1;i<=16;i++){putchar(num&mask?’1’:‘0’); /*輸出最高位的值(1/0)*/num<<=1; /*將次高位移到最高位上*/if(i%4==0)putchar(‘,’); /*四位一組，用逗號分開*/}

printf("\bB\n");} [例8.2]從鍵盤上輸入