このドキュメントは http://edu.net.c.dendai.ac.jp/ 上で公開されています。
線形リストとは図のような特殊な二分木でした。
値は葉にだけ入れられます。 左向きの枝には必ず葉が付きます。そして、特に、右の枝に付く葉には nil という値の葉が付きます。 このような構造にしておくと 「次の要素を取り出す」や、「今アクセスしている要素の隣に新しい要素を追 加」するなどは定数時間でできます。 但し、ランダムに「n 番目の値」を取り出すのは、順番 に走査しなければならないので、 程度の計算時間がかかります。 第 5 回でキュー、スタックを取り上げた際、 線形リストを利用しましたが、今回は線形リストをテーマにします。
さて、キューやスタックでは「次の値」という操作のみに注目していました。 一般に多くのデータを取り扱う場合、データをアクセスする統一的な手法があ ると便利です。 データは通常、繰り返し計算で順番にアクセスすることになります。 したがって、この「順番にアクセスする」という概念を抽象的にとらえると、 さまざまな大量データをアクセスする際に同じようなプログラムで処理できる ようになります。
要素を順番に取り出すための仕組みをイテレータ (Iterator 反復子) と呼びます。 これは要素を順々に指していくのでポインタのようなものになります。 プログラミング用語としてデータを指し示す「参照」「イテレータ」「ポイン タ」は次のような違いがあります。
参照とは、特定のオブジェクトを指すもの。あるいは格納先のメモリの番 地。
Java 言語ではオブジェクトの変数は参照を行う変数になる。 そのため、オブジェクト型の変数宣言してもオブジェクトの実体は生成されな い。 オブジェクトを使うためには new 演算子とコンストラクタの組などを使って オブジェクトを生成し、変数から参照するようにする。 関数呼び出しや、変数の代入において、参照がコピーされるだけでオブジェク トがコピーされないことに注意する必要がある。
一方、 C++ では変数宣言すると、基本型だろうがオブジェクトだろうが、全 て実体が作られる。 そのため、参照の機能が必要なときは意識して使用する。 C++ の参照変数は「型&」の形で宣言する。但し、何も指していない参照 変数は作れない。 そのため、初期化を伴う変数宣言、あるいは、関数宣言中にしか使用できない。 参照を作られる側には特に演算子は必要ない。 そのため、この仕組みより関数の変数呼び出しが可能になる。
#include <iostream>
int main(){
int a=3;
int& b=a;
int& c=b;
std::cout << a << b << c << std::endl;
c=4;b=5;a=6;
std::cout << a << b << c << std::endl;
}
C++ では関数呼び出しは通常値呼び出しになるため、オブジェクトを引数にし ても、オブジェクトがコピーされてしまう。 そのため、オブジェクトの変更を行わない場合でも通常は const 指定の参照 呼び出しを行う。
#include <iostream>
class Test {
private:
int x,y;
public:
Test(int _x, int _y){x=_x;y=_y;}
int getX() const {return x;}
int getY() const {return y;}
};
void show(const Test& t){
std::cout << t.getX() << t.getY() << std::endl;
}
int main(){
Test test(1,2);
show(test);
}
今回はこのイテレータという概念を導入して、線形リストの操作を考えたいと 思います。 なお、このイテレータは線形リストのみならずさまざまな大量のデータを格納 するデータ構造で実現されています。
さて、線形リストについて次のような操作を行うことを考えます。
また、C++, Java とも、リストに関して整列(順番に並べること) という機能も用意されています。 原理は次回に解説しますが、今回は整列の使い方についても解説します。
C++ ではすでに線形リストもそのイテレータも STL で提供されています。 したがって、上記の処理は特別なプログラムを組まなくても次のようにすれば 可能になります。以下はリストの中に文字列を入れる例です。
#include <string>
#include <list>
typedef std::list<std::string> stringList;
stringList aList;
stringList::iterator anIterator = aList.begin();
stringList::iterator anIterator = aList.end();
aList.push_back(要素);
aList.push_front(要素);
aList.empty()
aList.size()
aList.insert(aList.end(),anotherList.begin(),anotherList.end())
*anIterator;
++anIterator;
aList.insert(anIterator,要素);
aList.erase(anIterator);
aList.sort();
#include <string>
#include <iostream>
#include <list>
typedef std::list<std::string> stringList;
int main(){
stringList aList;
aList.push_back("abc");
aList.push_back("def");
aList.push_front("ghi");
for(stringList::iterator anIterator = aList.begin();
anIterator != aList.end(); ++anIterator){
std::cout << *anIterator << std::endl;
}
std::cout << "size = " << aList.size() << std::endl;
aList.sort();
while(!aList.empty()){
std::cout << *(aList.begin()) << std::endl;
aList.erase(aList.begin());
}
}
上の例では数の並び替えでは小さい順でしかできません。 しかし、様々な順序で並び替えたい場合もあります。 ここでは、任意の順番を与えて並び替えを行う例を示します。
整数を二進数に直した時、 1 となる桁の少ない順に数を並べることを考えま しょう。 例えば、 0 から 20 までだと次のようになります。
十進数 | 二進数 | 1 の数 |
---|---|---|
0 | 0 | 0 |
1 | 1 | 1 |
2 | 10 | 1 |
3 | 11 | 2 |
4 | 100 | 1 |
5 | 101 | 2 |
6 | 110 | 2 |
7 | 111 | 3 |
8 | 1000 | 1 |
9 | 1001 | 2 |
10 | 1010 | 2 |
11 | 1011 | 3 |
12 | 1100 | 2 |
13 | 1101 | 3 |
14 | 1110 | 3 |
15 | 1111 | 4 |
16 | 10000 | 1 |
17 | 10001 | 2 |
18 | 10010 | 2 |
19 | 10011 | 3 |
20 | 10100 | 2 |
したがって、 0 から 20 を並べると次のようになります。
0 個 | 1 個 | 2 個 | 3 個 | 4 個 |
---|---|---|---|---|
0, | 1, 2, 4, 8, 16, | 3, 5, 6, 9, 10, 12, 17, 18, 20, | 7, 11, 13, 14, | 15 |
これを C++ で作るには、まずビットの数を計算する関数を書きます。
#include <iostream>
int numOfBits(int n){
int k=0;
while(n>0){
k+=n%2;
n/=2;
}
return k;
}
int main(){
for(int i=0; i<=20; ++i){
std::cout << i << " " << numOfBits(i) << std::endl;
}
}
数を x, y とした時、 1 の数が x より y が大きい 時だけ true, そうでない時 false が返すような () オペレータをメソッドと してもつクラスを作ります。 但し、後で functional ヘッダファイル中の binary_function とシグネチャ を合わせる必要があるため、 int 型でも const の参照型にします。
#include <iostream>
int numOfBits(int n){
int k=0;
while(n>0){
k+=n%2;
n/=2;
}
return k;
}
class CompBit {
public:
bool operator()(const int& x, const int& y) const {
return numOfBits(x)<numOfBits(y);
}
};
int main(){
CompBit c; // 比較用オブジェクトの作成
for(int i=0; i<=20; ++i){
std::cout << i ;
for(int j=0; j<=20; ++j){
std::cout << " " << c(i,j);
}
std::cout << std::endl;
}
}
この CompBit クラスを利用して数を並べ替えます。 この時、functional をインクルードして CompBit を std::binary_function<int,int,bool> のサブク ラスにしておきます。
#include <iostream>
#include <list>
#include <functional>
int numOfBits(int n){
int k=0;
while(n>0){
k+=n%2;
n/=2;
}
return k;
}
class CompBit : public std::binary_function<int,int,bool> {
public:
bool operator()(const int& x, const int& y) const {
return numOfBits(x)<numOfBits(y);
}
};
template <typename T>
void showList(T& aList){
for(typename T::iterator anIterator = aList.begin();
anIterator != aList.end(); ++anIterator){
std::cout << *anIterator << " ";
}
std::cout << std::endl;
}
void horizonLine(){
std::cout << "---------------------------------------" << std::endl;
}
int main(){
CompBit c; // 比較用オブジェクトの作成
std::list<int> aList;
for(int i=0; i<=20; ++i){
aList.push_back(i);
}
showList(aList);
horizonLine();
aList.sort(c); // 比較用オブジェクトを使ったソート
showList(aList);
}
なお、template 内で T::iterator など、型の計算を示すためには typename を前に置く必要があります。 また、ここで showList の引数を const 宣言していないのは const 宣言した 引数に対する iterator は別の型(const_iterator)になってしまうからです。
なおこの比較専用のクラスをオブジェクトに対して作る場合、 private メン バへのアクセス権が欲しくなる場合があります。 このような場合、そのオブジェクトクラスに operator() を実装してしまう考 え方もありますが、比較するクラスのカプセル化の有無によって実装方法が異 なるのは不自然です。
このような場合、比較専用クラスに private メンバへのアクセスを特別に認 めてしまえば解決します。 そのため、元のオブジェクトのクラスに friend class でフレンド指定をしま す。
#include <functional>
class Example {
private:
int x;
int y;
public:
Example(int _x, int _y){x=_x; y=_y;}
friend class CompExample;
};
class CompExample : public std::binary_function<Example,Example,bool> {
public:
bool operator()(const Example& a, const Example& b) const {return a.y<b.y;}
};
オブジェクトに対して順番に並べることを考えます。 この場合も例7-2のように別の比較クラスを与えれば可能になります。 但し、比較クラスを与えずとも < 演算子、つまり operator< をクラス に実装しておけば、比較クラスを指定しなくても良くなります。 ここでは座標を原点に近い順に並べる例を示します。
#include <iostream>
#include <cmath>
#include <list>
class Point {
private:
double x,y;
public:
Point(double _x, double _y):x(_x),y(y){}
double distance() const {return std::sqrt(x*x+y*y);}
bool operator<(const Point& p) const { return distance()<p.distance();}
friend std::ostream& operator<<(std::ostream& os, const Point& p);
};
std::ostream& operator<<(std::ostream& os, const Point& p){
os << p.x << ',' << p.y;
return os;
}
template <typename T>
void showList(T& aList){
for(typename T::iterator i=aList.begin();
i!=aList.end(); ++i){
std::cout << *i << std::endl;
}
}
int main(){
std::list<Point> lp;
lp.push_back(Point(1,0));
lp.push_back(Point(3,4));
lp.push_back(Point(2,5));
lp.push_back(Point(1,1));
lp.push_back(Point(0,2));
showList(lp);
std::cout << "-------------------------"
<< std::endl;
lp.sort();
showList(lp);
}
Java では線形リストは java.util.LinkedList で提供されています。 これは、 iterator() メソッドをインプリメントしています。 なお、 C++ では Iterator はポインタと同じような文脈で作られてましたが、 Java では Iterator は一つのオブジェクトとして実装されます。
import java.util.*;
LinkedList<String> aList = new LinkedList<String>(); // Java 5
LinkedList aList = new LinkedList(); // Java 1.4
ListIterator<String> anIterator = aList.listIterator(); // Java 5
// listIterator() コンストラクタは aList の型 (LinkedList<String>)
// に従うので型の指定は不要
ListIterator anIterator = aList.listIterator(); // Java 1.4
aList.addLast(要素);
aList.addFirst(要素);
aList.isEmpty()
aList.size()
aList.addAll(anotherList);
String aString = anIterator.next(); // Java 5
Object anObject = anIterator.next(); // Java 1.4
anIterator.add(要素);
anIterator.remove();
java.util.Collections.sort(aList);
なおイテレータに関する構文をあげましたが、 Java 5 でリスト全要素にアク セスしたい場合は foreach 構文を使用した方が簡潔で安全です。
import java.util.*;
class TestList {
public static void main(String arg[]){
LinkedList<String> aList
= new LinkedList<String>();
aList.addLast("abc");
aList.addLast("def");
aList.addFirst("ghi");
for(String s : aList){ // foreach 構文
System.out.println(s);
}
System.out.println("size = " + aList.size());
java.util.Collections.sort(aList);
ListIterator<String> anIterator
= aList.listIterator();
while(!aList.isEmpty()){
System.out.println(anIterator.next());
anIterator.remove();
// Iterator のメソッドを使うので
// foreach は使わない
}
}
}
import java.util.*;
class TestList {
public static void main(String arg[]){
LinkedList aList = new LinkedList();
ListIterator anIterator;
aList.addLast("abc");
aList.addLast("def");
aList.addFirst("ghi");
anIterator =aList.listIterator();
while(anIterator.hasNext()){
String s = (String) anIterator.next();
System.out.println(s);
}
System.out.println("size = " + aList.size());
java.util.Collections.sort(aList);
anIterator = aList.listIterator();
while(!aList.isEmpty()){
String s = (String) anIterator.next();
System.out.println(s);
anIterator.remove();
}
}
}
ここでも例7-2同様に、 Java において、任意の順序を指定して並び替えを行 うことを考えましょう。 そのため、 Java ではまず、 1 の数を計算する関数を持つクラスを作ります。
class CompBit {
static int numOfBits(int n){
int k=0;
while(n>0){
k+=n%2;
n/=2;
}
return k;
}
public static void main(String[] args){
for(int i=0; i<=20; i++){
System.out.println(i+" "+numOfBits(i));
}
}
}
そして、java.util.Collections.sort() を使うため、java.util.Comparator インタフェースをインプリメントします。 Comparator インタフェースの定義は以下の通りです。
public interface Comparator<T> {
public int compare(T o1, T o2);
public boolean equals(Object obj);
}
public interface Comparator {
public int compare(Object o1, Object o2);
public boolean equals(Object obj);
}
したがって作成している CompBit クラスに Comparator インタフェースをイ ンプリメントするには compare メソッドと equals メソッドを実装します。
class CompBit implements java.util.Comparator<Integer> {
static int numOfBits(int n){
int k=0;
while(n>0){
k+=n%2;
n/=2;
}
return k;
}
public int compare(Integer o1, Integer o2){
int r1=CompBit.numOfBits(o1);
int r2=CompBit.numOfBits(o2);
return (r1<r2)?-1:(r1==r2)?0:1;
}
public boolean equals(Object obj){
return false;
}
}
class TestComp {
public static void main(String[] args){
CompBit c=new CompBit();
for(int i=0; i<=20; i++){
System.out.print(i);
for(int j=0; j<=20; j++){
System.out.print(" "+c.compare(i,j));
}
System.out.println();
}
}
}
class CompBit implements java.util.Comparator {
static int numOfBits(int n){
int k=0;
while(n>0){
k+=n%2;
n/=2;
}
return k;
}
public int compare(Object o1, Object o2){
int r1=CompBit.numOfBits(((Integer)o1).intValue());
int r2=CompBit.numOfBits(((Integer)o2).intValue());
return (r1<r2)?-1:(r1==r2)?0:1;
}
public boolean equals(Object obj){
return false;
}
}
class TestComp {
public static void main(String[] args){
CompBit c=new CompBit();
for(int i=0; i<=20; i++){
System.out.print(i);
Integer anInteger=new Integer(i);
for(int j=0; j<=20; j++){
System.out.print(" "+c.compare(anInteger, new Integer(j)));
}
System.out.println();
}
}
}
そして、線形リストに対して java.util.Collections.sort() で整列します。
class CompBit implements java.util.Comparator<Integer> {
static int numOfBits(int n){
int k=0;
while(n>0){
k+=n%2;
n/=2;
}
return k;
}
public int compare(Integer o1, Integer o2){
int r1=CompBit.numOfBits(o1);
int r2=CompBit.numOfBits(o2);
return (r1<r2)?-1:(r1==r2)?0:1;
}
public boolean equals(Object obj){
return false;
}
}
class TestComp {
private static <T> void showList(java.util.List<T> aList){
for(T i : aList){
System.out.print( i.toString() + " ");
}
System.out.println();
}
private static void horizonLine(){
System.out.println("---------------------------------------");
}
public static void main(String[] args){
CompBit aComparator = new CompBit();
java.util.LinkedList<Integer> aList
= new java.util.LinkedList<Integer>();
for(int i=0; i<=20; i++){
aList.addLast(i);
}
showList(aList);
horizonLine();
java.util.Collections.sort(aList, aComparator);
showList(aList);
}
}
class CompBit implements java.util.Comparator {
static int numOfBits(int n){
int k=0;
while(n>0){
k+=n%2;
n/=2;
}
return k;
}
public int compare(Object o1, Object o2){
int r1=CompBit.numOfBits(((Integer)o1).intValue());
int r2=CompBit.numOfBits(((Integer)o2).intValue());
return (r1<r2)?-1:(r1==r2)?0:1;
}
public boolean equals(Object obj){
return false;
}
}
class TestComp {
private static void showList(java.util.List aList){
for(java.util.Iterator anIterator = aList.iterator();
anIterator.hasNext();){
System.out.print(anIterator.next().toString()+" ");
}
System.out.println();
}
private static void horizonLine(){
System.out.println("---------------------------------------");
}
public static void main(String[] args){
CompBit aComparator = new CompBit();
java.util.LinkedList aList = new java.util.LinkedList();
for(int i=0; i<=20; i++){
aList.addLast(new Integer(i));
}
showList(aList);
horizonLine();
java.util.Collections.sort(aList, aComparator);
showList(aList);
}
}
C++ と同様に、オブジェクトに対して順番に並べることを考えます。
この場合も別の比較クラスを与えれば可能になります。
但し、比較クラスを与えずとも java.lang.Comparable インタフェースを
implement すれば比較クラスを指定しなくても良くなります。
具体的には、クラス宣言時に implements Comparable
を指定し、
public int compareTo(
ここでは例7-3 同様に座標を原点に近い順に並べる例を示します。
import java.util.*;
class Point implements Comparable<Point>{
double x;
double y;
public Point(double _x, double _y){ x=_x; y=_y;}
public double distance(){return Math.sqrt(x*x+y*y);}
public int compareTo(Point p){
if(distance()==p.distance()){return 0;}
if(distance()<p.distance()){ return -1;}
return 1;
}
public String toString(){
return Double.toString(x)+", "+Double.toString(y);
}
}
class Test {
private static <T> void showList(List<T> aList){
for(T i : aList){
System.out.println(i.toString());
}
}
public static void main(String[] args){
LinkedList<Point> lp = new LinkedList<Point>();
lp.addLast(new Point(1,0));
lp.addLast(new Point(3,4));
lp.addLast(new Point(2,5));
lp.addLast(new Point(1,1));
lp.addLast(new Point(0,2));
showList(lp);
System.out.println("-------------------------");
Collections.sort(lp);
showList(lp);
}
}
C++ や Java では線形リストがあらかじめ用意されていましたが、 C 言語に はありません。そこで、ポインタや構造体を使って実現する必要があります。
線形リストでは左の枝には必ず値を持つ頂点が付くので、左の枝を作る代わり に値を直接入れることにします。 右の枝はそのまま別の頂点を指すことにしますので、頂点を作る構造体は、左 の枝を意味する場所には値を入れ、右の枝を表す場所には別の頂点へのポイン タを入れることにします。 線形リストの頂点の構造体を定義すると次のようになります。
typedef struct lst {
char *item;
struct lst *next;
} LIST;
このようにして作った構造体をメモリ上に作り、next フィールドに次の頂点 の番地を入れて連結します。 ところで、リストの最後の nil を含んだ葉も同じ頂点である必要があります。 そこで、 next フィールドに NULL が入っていることとして表現することにし ます。 すると、空のリストは NULL が入った頂点だけで表現することになります。 一方、プログラム内でリストを扱うには、先頭の頂点へのポインタを持ちます。 したがって、プログラムで空のリストを作るには、次のようにします。
LIST *aNode = malloc(sizeof(LIST));
aNode->next=NULL;
線形リストの先頭に文字列の要素を付け足す関数 addfirst(LIST *firstNode, char *str) は次のよう処理を行います。
まず、C 言語は値呼出しなので、関数の引数に含まれている先頭の 頂点へのポインタ firstNode は変更できません。 これは先頭の頂点のアドレスは変更できないことを意味します。 ですから、新たな要素 *str は既存の頂点へ代入されることになります。 したがって、付け足すべき新たな頂点の領域を確保したら、この領域は既存の 現在の先頭の要素が入ることになります。 つまり、新しい頂点の領域を確保したらその頂点は二番目の頂点にな るようにします。
新しい頂点の next フィールドは三番目、つまり付け足す前では二番目の頂点 を指すようにします。これは付け足す前では先頭の next フィールドに入って いたアドレスになります。
したがって処理をまとめると次のようになります。
int addfirst(LIST *firstNode, char *str){
LIST *newNode;
if((newNode=malloc(sizeof(LIST)))==NULL){
return 0;
}
newNode->item = firstNode->item;
newNode->next = firstNode->next;
firstNode->item = str;
firstNode->next = newNode;
return 1;
}
一方、リストの最後に文字配列の要素を付け足す関数 addend(LIST *firstNode, char *str) は、nil 頂点を探して、その頂点に新しい要素を入れ、新たに作っ た nil 頂点を指すようにします。
int addend(LIST *firstNode, char *str){
LIST *newNode, *p;
if((newNode=malloc(sizeof(LIST)))==NULL){
return 0;
}
p=firstNode;
while(p->next != NULL){
p = p->next;
}
p->item = str;
p->next = newNode;
newNode->next = NULL;
return 1;
}
最初に付け加えるのと違い、リストすべての要素を見なければならないので、 計算時間が余計にかかっていることに注意して下さい。
リストの各要素に対して、単純に指している頂点を削除すると、その頂点を指 す手前の頂点が次の頂点を指すようにできません。 そのため、特定の要素を消す場合、他の接続関係を調整してやる必要がありま す。 また、先頭の要素を連続して消したい場合を考えると、リストの先頭を指すデー タは消えても、領域が消えては次の先頭を探すことができません。 そのため、先頭の領域は消さず、その領域に次のデータが入っているようにす る必要があります。 したがって、領域としてはその次の頂点の領域を消すことにし、消 す前に次の頂点の持つ情報を現在指している領域にコピーすることとします。
void removenode(LIST *aNode){
LIST *deleteNode = aNode->next;
aNode->item = deleteNode->item;
aNode->next = deleteNode->next;
free(deleteNode);
}
#include <stdio.h>
#include <stdlib.h>
typedef struct lst {
struct lst *next;
char *item;
} LIST;
void addend(LIST *pointer, char *i){
LIST *newnode=malloc(sizeof(LIST));
newnode->next=NULL;
while(pointer->next != NULL){
pointer = pointer->next;
}
pointer->next=newnode;
pointer->item=i;
}
void addfirst(LIST *pointer, char *i){
LIST *newnode=malloc(sizeof(LIST));
newnode->next=pointer->next;
newnode->item=pointer->item;
pointer->next=newnode;
pointer->item=i;
}
int empty(LIST *pointer){
return pointer->next == NULL;
}
int size(LIST *pointer){
LIST *p=pointer;
int i=0;
while(p->next != NULL){
p=p->next;
i++;
}
return i;
}
void removeitem(LIST *pointer){
LIST *d=pointer->next;
pointer->item=d->item;
pointer->next=d->next;
/* free((pointer->next)->item) */
free(d);
}
void showItem(LIST *p){
while(p->next!=NULL){
printf("%s\n",p->item);
p=p->next;
}
printf("\n");
}
int main(void){
LIST *firstNode=malloc(sizeof(LIST));
firstNode->next=NULL;
addend(firstNode,"abc");
addend(firstNode,"def");
addfirst(firstNode,"ghi");
showItem(firstNode);
printf("size = %d\n",size(firstNode));
while(!empty(firstNode)){
showItem(firstNode);
removeitem(firstNode);
}
return 0;
}
線形リストも配列も複数のものを格納することができますが、それぞれにおい て処理の効率が変わります。 従って、用途に応じて選択する必要があります。
配列はメモリの連続した領域を確保し、 n 番目の要素へのアクセスを許しま す。 n 番目の要素へのアクセスは既に紹介したように、 でアドレスを計算します。 従って、時間計算量は n を計算する手間になります。 これは n の桁数に比例した時間かかります。 要素数が最大 N だとすると、全体の時間計算量は になります。 一方、特定の位置(先頭など)に要素を挿入したり、削除したりするには全部の 要素をずらす必要があります。 一つの要素をずらすのに定数時間で済んでも、最大で全要素数 N に比例する 時間だけかかります。 従って、全体の時間計算量は になります。
線形リストでは n 番目の要素にアクセスするには、基本的には先頭から順に 見ていくしかありません。 従って、時間計算量は になります。 しかし、一方、特定の位置に要素を挿入したり、削除したりするには、メモリ の適当な位置に頂点を確保し、リンクをつなげるだけなので、 の時間計算量で済みます。
以上のように要素へのランダムアクセスが必要な時は配列、要素の追加、削除 が頻繁な時は線形リストが有利なことが分かります。
ランダムアクセス | 要素の追加、削除 | |
---|---|---|
配列 | ||
線形リスト |
双方向リストとは、次の頂点へのポインタと前の頂点へのポインタの両方を保 持するものです。 特定の頂点に注目して処理する場合に便利です。 エディタなど、特定の行に注目した処理をするのに用いられます。 実は C++ の list, Java の LinkedList のどれも双方向リストです。 C++ では Iterator に対して -- 演算が可能です。 一方、Java では java.util.ListIterator には previous() メソッドが用意 されています。
双方向リストを使って less を作りなさい。 less とは more を拡張したコマンドで、次の動作をします。
main 関数を
int main(int argc, char* argv[])
で指定すると、コマンドライ
ンで文字列をプログラムに渡せるようになります。
コマンドラインになにも指定しないと、 argc が 1 になり、第二引数の char
*argv[] の argv[0] に起動コマンド名が入ります。
起動時にコマンド(.\a.exe) の後ろに文字列を空白で区切ると、それぞれが
argv[] の配列に入ります。
#include <stdio.h>
int main(int argc, char * argv[]){
int i;
if(argc==1){
printf("Usage: %s filename ...\n",argv[0]);
return 2;
}
printf("起動コマンド %s\n",argv[0]);
for(i=1;i<argc;i++){
printf("引数 %d = %s\n",i,argv[i]);
}
return 0;
}
#include <stdio.h>
#include <stdlib.h>
typedef struct blst {
struct blst *next;
struct blst *previous;
char *item;
} BLIST;
int add(BLIST *base, BLIST *pointer, char *i){
BLIST *newnode;
if((newnode=malloc(sizeof(BLIST)))==NULL){
return 0;
}
newnode->item = i;
newnode->next = pointer->next;
if(pointer->next == NULL){
newnode->previous = base->previous;
base->previous = newnode;
}else{
newnode->previous = (pointer->next)->previous;
(pointer->next)->previous = newnode;
}
pointer->next = newnode;
return 1;
}
void printlist(BLIST *base){
BLIST *p=base;
while((p=p->next)!=NULL){
printf("%s ",p->item);
}
printf("\n");
}
void printreverse(BLIST *base){
BLIST *p=base;
while((p=p->previous)!=NULL){
printf("%s ",p->item);
}
printf("\n");
}
int empty(BLIST *base){
return base->next == NULL;
}
int size(BLIST *base){
BLIST *p=base;
int i=0;
while((p=p->next) != NULL){
i++;
}
return i;
}
int removenode(BLIST *base, BLIST *pointer){
BLIST *p,*n;
if(base==pointer){
return 0;
}
p = pointer->previous;
n = pointer->next;
if(p==NULL){
base->next = n;
}else{
p->next = n;
}
if(n==NULL){
base->previous = p;
}else{
n->previous = p;
}
/* free(pointer->item) */
free(pointer);
return 1;
}
void showCondition(BLIST *bList){
printlist(bList);
printreverse(bList);
printf("size = %d\n",size(bList));
}
#define errorCheck(func) if(!(func))exit(1)
int main(void){
BLIST *l;
errorCheck((l=malloc(sizeof(BLIST)))!=NULL);
BLIST *p;
l->next=l->previous=NULL;
errorCheck(add(l,l,"abc"));
showCondition(l);
errorCheck(add(l,l,"def"));
showCondition(l);
errorCheck(add(l,l->previous,"ghi"));
showCondition(l);
errorCheck(add(l,l->previous,"jkl"));
showCondition(l);
errorCheck(add(l,l->next->next->next,"mno"));
showCondition(l);
while(!empty(l)){
showCondition(l);
removenode(l, l->next);
}
return 0;
}