鏈表及位運(yùn)算

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

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

節(jié)點(diǎn)的定義

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

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

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

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

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

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

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

typedef

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

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

NODE*head; /*說(shuō)明頭指針head*/在Ｃ語(yǔ)言中，用結(jié)構(gòu)類型來(lái)描述結(jié)點(diǎn)結(jié)構(gòu)。例：建立和輸出一個(gè)簡(jiǎn)單鏈表#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;/*對(duì)結(jié)點(diǎn)的num和score成員賦值*/head=&a;/*將結(jié)點(diǎn)a的起始地址賦給頭指針head*/head99101

89.5a99103

90b99107

85

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

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

8.1

位運(yùn)算和位運(yùn)算符

8.2

位運(yùn)算舉例

8.1位運(yùn)算一、位運(yùn)算及其運(yùn)算符

1．按位與──&

(1)格式：x&y

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

2．按位或──

|

(1)格式：x|y

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

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

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

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

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

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

2）按需要進(jìn)行左移或右移操作，構(gòu)造出所需要的數(shù)?；舅悸罚海?）使變量num右移8位，將8～11位移到低4位上。（2）構(gòu)造1個(gè)低4位為1、其余各位為0的整數(shù)。（3）與num進(jìn)行按位與運(yùn)算。/*程序功能：輸出一個(gè)整數(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個(gè)低4位為1、其余各位為0的整數(shù)*/

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

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

printf("Inputaintegernumber:");

scanf("%d",&num);mask=1<<15;/*構(gòu)造1個(gè)最高位為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(‘,’); /*四位一組，用逗號(hào)分開(kāi)*/}

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