計(jì)算機(jī)軟件基礎(chǔ)
實(shí)驗(yàn)一：線性表／棧與隊(duì)
一、實(shí)驗(yàn)?zāi)康?/span>
了解實(shí)現(xiàn)線性表／棧與隊(duì)／數(shù)組所涉及到的數(shù)據(jù)結(jié)構(gòu)。
二、實(shí)驗(yàn)要求
因受時(shí)間限制，從以下給出的4個(gè)實(shí)驗(yàn)內(nèi)容中任選3個(gè)，分析并補(bǔ)齊給出的源程序，運(yùn)行相應(yīng)的程序，檢驗(yàn)運(yùn)行結(jié)果,以此鞏固對(duì)相應(yīng)部分的理論知識(shí)的理解。
1．復(fù)習(xí)線性表、棧與隊(duì)列的定義，理解順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)的方法及基本操作。
2．復(fù)習(xí)C語言中數(shù)組、指針及結(jié)構(gòu)體的概念、定義方式。
3．上機(jī)前準(zhǔn)備好全部源程序。
4．計(jì)算機(jī)中需要安裝vc6.0或vs2010。
5．程序中所用結(jié)構(gòu)體定義于datastru.h中。
三、實(shí)驗(yàn)內(nèi)容
熟悉vs2010環(huán)境下建立程序源文件與調(diào)試程序的流程。
1、完成有序表(順序表)中插入一元素并保證仍然有序。
……(補(bǔ)充程序)
void main( )
{
SEQUENLIST ?L;
int num,i,k,x;
L.last=0; ??//置順序表為空,表長為0
printf("請(qǐng)輸入順序表元素，元素為整型量，用空格分開，-99為結(jié)束標(biāo)志：");
/*輸入順序表元素,建立有序表,值從小到大*/
scanf("%d",&num);
while (num !=-99) {
………(補(bǔ)充程序)
L.last++;
scanf("%d",&num);
}
printf("%d",L.last);
printf("輸入要插入的元素值(整型) : ");
scanf("%d",&num);
printf("\n插入前有序表元素列表 ：");
for (i=0; i<L.last; i++)
?printf("%4d",L.datas[i]);
printf("\n");
k = L.last-1;
while ((k>= 0) && (num<L.datas[k])) /*查找插入位置i ?*/
k--;
for(i=L.last-1; i>=k+1; i--)
L.datas[i+1]=L.datas[i]; ?/*移動(dòng)元素 ?*/
L.datas[k+1]=num; ????????????????????????????????????/*新元素插入*/
L.last++; ????????????????????????????????????????????/*表長加1 */
printf("\n插入后有序表元素列表 ：");
for (i=0; i<L.last; i++)
?printf("%4d",L.datas[i]);
printf("\n");
}
?
2、完成鏈表的結(jié)點(diǎn)插入、刪除操作，并顯示操作前后的線性表中各元素的情況。
……(補(bǔ)充程序)
?
void inser_order(DATATYPE2 x, LINKLIST *head){
LINKLIST *pr, *pn, *pp;
pr = head; pn = head->next;
while(pn != NULL && pn->data < x)
{
……(補(bǔ)充程序)
}
pp = (LINKLIST *)malloc(sizeof(LINKLIST));
……(補(bǔ)充程序)
}
?
int count_head(LINKLIST *head)?????/*輸出單鏈表元素值并計(jì)數(shù)*/
{
int i = 0;
LINKLIST *p;
p = head->next;
printf("輸出單鏈表元素值 : ");
while(p != NULL)
{
……(補(bǔ)充程序)
}
printf("\n");
return i;
}
?
LINKLIST *creatlink_order_head(LINKLIST *head) ??/*建立帶頭結(jié)點(diǎn)的有序單鏈表*/
{
LINKLIST *t, *p, *q;
char ch;
t = (LINKLIST *)malloc(sizeof(LINKLIST)); ??//建立帶頭結(jié)點(diǎn)的空鏈表
t->next = NULL;
head = t;
printf("單鏈表元素值為單個(gè)字符, 連續(xù)輸入，#為結(jié)束字符 ?: ");
while ((ch = getchar()) != '#')
{
……(補(bǔ)充程序)
}
return head;
}
?
int main()
{
LINKLIST *head = NULL;
int ?num;
char ch;
printf("\n????建立單鏈表\n\n");
head = creatlink_order_head(head);
num = count_head(head);
printf("單鏈表元素個(gè)數(shù) = %d\n", num);
fflush(stdin);
printf("\n輸入插入元素值 : ");
ch = getchar();
inser_order(ch, head);
printf("\n ???元素插入后\n\n");
num = count_head(head);
printf("插入后單鏈表元素個(gè)數(shù) = %d\n", num);
return 1;
}
?
3、運(yùn)用棧完成十進(jìn)制數(shù)與八進(jìn)制數(shù)的轉(zhuǎn)換。
……(補(bǔ)充程序)
void initstack(SEQSTACK *s) ??/*順序棧初始化*/
{
?……(補(bǔ)充程序)
}
?
DATATYPE1 gettop(SEQSTACK *s) /*返回棧頂元素*/
{
???DATATYPE1 ?x;
???……(補(bǔ)充程序)
???return x;
?}
?
int push(SEQSTACK ??*s, ?DATATYPE1 ?x) ?/*元素x入棧*/
{
??if(s->top == MAXSIZE-1)
??{
?……(補(bǔ)充程序)
??}
??else
??{
??……(補(bǔ)充程序)
??return 1;
??}
}
?
DATATYPE1 pop(SEQSTACK *s) ???/*返回棧頂元素并刪除棧頂元素*/
{
DATATYPE1 ?x;
if(s->top == 0)
{
printf("?？誠n");
x=0;
}
else
{
……(補(bǔ)充程序)
}
?
return ?x;
}
?
int main( )
{
SEQSTACK stack, *s;
int ?n;
s = &stack;
initstack(s);
n = 0;
printf("輸入一非負(fù)整數(shù)(十進(jìn)制) ：");
scanf("%d",&n);
push(s,'#');
while(n != 0)
{
push(s, n % 8); ????????/* %為求余數(shù)運(yùn)算符, 余數(shù)入棧*/
n = n / 8; ? ?/* /為求整數(shù)商運(yùn)算符,商不為零,繼續(xù)運(yùn)行*/
} ????????????
?
printf("\n\n對(duì)應(yīng)的八進(jìn)制數(shù)為 ：");
while(gettop(s) != '#')
printf("%d",pop(s));
printf("\n");
?
return 1;
}
?
4、實(shí)現(xiàn)帶頭結(jié)點(diǎn)鏈隊(duì)元素的刪除、插入操作，并顯示操作前后的隊(duì)列情況。
……(補(bǔ)充程序)
DATATYPE1 dellinkqueue(LINKQUEUE *q) ???/*刪除隊(duì)頭元素并返回*/
{
……(補(bǔ)充程序)
if(q->front == q->rear)
{
printf("隊(duì)列空\n");
v = 0;
}
else
{
……(補(bǔ)充程序)
}
return v;
}
void enlinkqueue(LINKQUEUE *q, DATATYPE1 x) ?/*元素x 入隊(duì)列*/
{
(q->rear)->next = (LINKQLIST *)malloc(sizeof(LINKQLIST));
……(補(bǔ)充程序)
}
?
void initlinkqueue(LINKQUEUE *q) ?/*鏈隊(duì)列初始化*/
{
……(補(bǔ)充程序)
}
?
void outlinkqueue(LINKQUEUE *q) ????/*鏈隊(duì)列元素依次顯示*/
{
LINKQLIST *p;
p = q->front;
printf("隊(duì)列元素顯示 : ");
while(p != q->rear)
{
……(補(bǔ)充程序)
}
printf("\n");
}
?
int main()
{
LINKQUEUE lq, *p;
int j;
p = &lq;
initlinkqueue(p);
printf("輸入一整數(shù)(奇數(shù)——入隊(duì)列、偶數(shù)——?jiǎng)h除隊(duì)頭元素、0——退出) : ");
scanf("%d", &j);
while(j != 0) ???????????????????/*輸入 0——退出*/
{
if(j % 2 == 1) ?????????????
enlinkqueue(p,j); ???????????/*輸入奇數(shù)——入隊(duì)列*/
else
j = dellinkqueue(p); ?????????/*輸入偶數(shù)——?jiǎng)h除隊(duì)頭元素*/
outlinkqueue(p);
????printf("\n輸入一整數(shù)(奇數(shù)——入隊(duì)列、偶數(shù)——?jiǎng)h除隊(duì)頭元素、0——退出) : ");
????scanf("%d", &j); ????????????/*繼續(xù)輸入*/
}
?
return 1;
}
四、注意事項(xiàng)
注意程序中用到的結(jié)構(gòu)體的來源及表示方法、調(diào)用方式。讀懂程序結(jié)構(gòu)，先補(bǔ)齊缺失代碼，再調(diào)試運(yùn)行程序。
五、實(shí)驗(yàn)總結(jié)和體會(huì)
?
?
?
?
