PTA題目：順序表---插入結點

建立順序表，在順序表中插入一個結點。 順序表結構定義如下：

typedef char ElemType;
typedef struct 
{
	ElemType data[MaxSize];
   	int length;
} SqList;

要求寫出：

void DispList(SqList *L);  //輸出順序表,每個結點之間空格符間隔。
bool ListInsert(SqList *&L,int i,ElemType e);  //在順序表第i個位置上插入一個結點，插入成功時，返回TRUE,否則返回FALSE.

函數介面定義

void InitList(SqList *&L);	//初始化線性表  .由裁判程式實現。
void DispList(SqList *L);  //輸出順序表,每個結點之間空格符間隔。
bool ListInsert(SqList *&L,int i,ElemType e);  //在順序表第i個位置上插入一個結點，插入成功時，返回TRUE,否則返回FALSE.

裁判測試程式樣例：

#include <stdio.h>
#include <malloc.h>
#define MaxSize 1000
typedef char ElemType;
typedef struct 
{
	ElemType data[MaxSize];
   	int length;
} SqList;
void InitList(SqList *&L);	//初始化線性表
void DispList(SqList *L);
bool ListInsert(SqList *&L,int i,ElemType e);

int main()
{
	SqList *L;
	ElemType e,ch;
	int i=1;
	InitList(L);
	while((ch=getchar())!='\n')
	{
		ListInsert(L,i,ch);  //在L的第i個元素位置上插入ch
		i++;
	}
	DispList(L);
	scanf("\n%d %c",&i,&ch);
	if ( ListInsert(L,i,ch))
			DispList(L);
}

/* 請在這裡填寫答案 */

輸入樣例：

在這裡給出一組輸入。例如：

abcdefghijk
5 X

輸出樣例：

在這裡給出相應的輸出。例如：

a b c d e f g h i j k 
a b c d X e f g h i j k 

分析

插入部分是個很基礎的陣列插入，首先從最後一個數位開始往後移，直到把第i個數位也移動完成。這裡需要注意的是一個界限的問題，當i<1或者i比總長度加一還大，連結串列總長度已經達到MaxSize時，與題意想違背。應當去除這些情況。後面有一個格式問題，筆者也出過這個問題了，輸出完畢後應該輸出一次換行，因為每個樣例要用到兩次輸出函數，這兩次的輸出值是分行的。

答案

bool ListInsert(SqList *&L,int i,ElemType e){
	int k;
    if(i < 1 || i > L->length+1|| L->length == MaxSize)return false;
	for(k=L->length;k>=i;k--){
		L->data[k]=L->data[k-1];
	}
	L->data[i-1]=e;
	L->length++;
	return true;
}
void DispList(SqList *L){
	int t;
	for(t=0;t<L->length;t++){
		printf("%c ",L->data[t]);
	}
    printf("\n");
}

如果覺得博主寫得不錯的話，就點個贊或者關注吧！